CODEWITHSUNDEEP
javaperformanceprimes
user10516751
user10516751

Reputation:

How to check if a 10 digit number is prime or not?

I know about Sieve's Algorithm and that I was using until now to get prime numbers for upto 1 billion.

But now I need to know if a 10 digit number is prime or not, and Sieve's algorithm can't compute that within time limit.

I searched a lot and came upon Fermat's prime testing, but it didn't work out, as some part I couldn't understand and other part told that it only tells if it's probable prime or not with some iteration.

I want to know how can I test if a number that big is prime or not, under 1 second or so? What would be the most efficient solution/algorithm for this?

Edit I am also adding my code for Sieve's algorithm.

public class Random18 {

    public static int sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and initialize 
        // all entries it as true. A value in prime[i] will 
        // finally be false if i is Not a prime, else true. 
        boolean primes[] = new boolean[n+1]; 
        Arrays.fill(primes,true);        // assume all integers are prime.

        primes[0]=primes[1]=false;       // we know 0 and 1 are not prime.
        for (int i=2;i<primes.length;i++) {
            //if the number is prime, 
            //then go through all its multiples and make their values false.
            if(primes[i]) {
                for (int j=2;i*j<primes.length;j++) {
                    primes[i*j]=false;
                }
            }
        }
        if(primes[n]==true)
            return 1;

        else
            return 0;
    } 


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter");

        int p = scanner.nextInt();

        long t1 = System.currentTimeMillis();

        int k = sieveOfEratosthenes(p);

        long t2 = System.currentTimeMillis();

        if(k==1)
            System.out.println("yes");

        else
            System.out.println("no");

        System.out.println("took "+(t2-t1)+" millis");


        scanner.close();
    }

}

Output for big numbers like this:
999999937
yes
took 24363 mills

Upvotes: 0

Views: 1284

Answers (5)

maaartinus
maaartinus

Reputation: 46482

It's inefficient to create the sieve just for testing a few numbers. A ten digit number is rather small in this context as if it's a non-prime, it must have a divisor between two and sqrt(9_999_999_999). So you check if it's even and then there are 50k divisor candidates to check.

If you don't want to do it yourself, there's BigInteger.valueOf(x).isProbablePrime(certainty) directly in the JDK. There's also LongMath.isPrime(long x) in Guava.

Upvotes: 1

Yuan
Yuan

Reputation: 370

I always use this code to check if an int is prime

boolean isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Upvotes: 1

Waqas Gondal
Waqas Gondal

Reputation: 477

You can check either it is a prime number or not:

public class Prime {

public static void main(String[] args) {

    int num = 10;
    boolean flag = false;
    for(int i = 2, max = num/2; i <= max; ++i)
    {
        // condition for nonprime number
        if(num % i == 0)
        {
            flag = true;
            break;
        }
    }

    if (!flag)
        System.out.println(num + " is a prime number.");
    else
        System.out.println(num + " is not a prime number.");
}}

Upvotes: 2

Oleg Cherednik
Oleg Cherednik

Reputation: 18255

public static void main(String[] args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Enter: ");
        long val = scan.nextLong();
        long t1 = System.currentTimeMillis();
        System.out.println(isPrime.test(val) ? "yes" : "no");
        System.out.println("took " + (System.currentTimeMillis() - t1) + " millis");
    }
}

static final LongPredicate isPrime = val -> {
    if (val < 2)
        return false;

    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
        if (val % i == 0)
            return false;

    return true;
};

Output:

Enter: 999999937
yes
took 1 millis

Upvotes: 2

Sandeepa
Sandeepa

Reputation: 3755

This method skip all even numbers and only try up to the square root of the number. It is working fine for your given number

public class Prime {
    public static void main(String[] args) {
        isPrime(999999937L);
    }

    public static boolean isPrime(long num) {
        if (num > 2 && num % 2 == 0) {
            System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                System.out.println(num + " is not prime");
                return false;
            }
        }
        System.out.println(num + " is prime");
        return true;
    }
}

I have taken it from here

Upvotes: 0

Related Questions