-1

How to implement an efficient code in java to verify whether a given number is a prime number or not for number's of size greater than or equal to 12 digits?

Example

Input:
100123456789
Output: prime
Input:
101111111111
Output: prime
Input:
101740496633
Output: prime
Input:
111111111111
Output:not prime
Input:
157639024808
Output: not prime

I tried implementing the following algorithm to find whether it is prime or not. But it is not working taking too long for numbers with greater than or equal to 12 digits.

My Code

public static Boolean checkPrime(long a){
    if(a%2==0)
        return false;
    for(int i=3;i<(int)Math.sqrt(a);i=i+2){
        if(a%i==0){
            return false;
        }
    }
    return true;    
}

'a' is the number to be checked
The above function returns true if the given number is prime or false if the given number is not prime.

How to find whether a given number is prime or not for numbers of size greater than 12?

user207421
  • 305,947
  • 44
  • 307
  • 483
KNV Srinivas
  • 61
  • 2
  • 10
  • 5
    Use `long` instead of `int`. – PM 77-1 Mar 27 '16 at 22:24
  • 2
    Your method returns the wrong answer when the argument is `2`, too. – John Bollinger Mar 27 '16 at 22:26
  • 4
    Your method may also fail when `a` is a square. – John Bollinger Mar 27 '16 at 22:28
  • 1
    Try the Miller-Rabin test. It take just a few dozen lines to implement and it is drastically more efficient than trial division. Wiki the test to see what it is. It is probabilistic, but only numbers 15 digits and up are false positives for bases a = 2, 3, 5, 7, 11, 13, and 17, so it is deterministic for those bases for 14 digits and less. You can get other base/size guarantees on the wiki page for the test. There are base combinations that grantee all 64 bit numbers to be deterministically tested. – Kyle Mar 27 '16 at 22:29
  • 5
    `BigInteger.isProbablePrime()` ? – vlp Mar 27 '16 at 22:32
  • If you're searching for an algorithm that is better than simple division test, then read something like this: https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests – Andreas Mar 27 '16 at 22:40
  • How can a prime number be a square?John Bollinger and more over it is just a function to check for numbers greater than 10000 – KNV Srinivas Mar 27 '16 at 23:10
  • @Andreas, fast deterministic tests are terribly slow compared to probabilistic tests, and so if you have a limited range where probabilistic tests become deterministic in a known way, that is a much better way to go. If input is, say, a 64 bit integer, then you are already in such a situation. Additionally, implementing a fast deterministic test is no small project. – Kyle Mar 27 '16 at 23:31
  • Thanks Kyle miller-rabin test worked fine for me up to an extent. – KNV Srinivas Mar 27 '16 at 23:34
  • I don't see any reason why this code wouldn't work for more than 12 digits, unless you have an `int` somewhere. It should work up to 19 digits. Do you mean that it just takes too long? – user207421 Mar 28 '16 at 00:14
  • Yes it takes too long to give the required output – KNV Srinivas Mar 28 '16 at 00:16
  • see [Prime numbers by Eratosthenes quicker sequential than concurrently?](http://stackoverflow.com/a/22477240/2521214) you can combine more methods together ... periodic sieves + memoized primes division test + some stochastic test if you want more speed. – Spektre Mar 28 '16 at 07:32
  • @KNV So that's what it should say in your question. 'Not working' is simply untrue. – user207421 Mar 29 '16 at 01:30

1 Answers1

2

You can speed this up slightly by only checking 1/3 of values instead 1/2.

public static boolean checkPrime(long a) {
    if (a % 2 == 0)
        return a == 2;
    for (int i = 3; i <= (int) Math.sqrt(a); i = i + 2) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}

public static boolean checkPrime2(long a) {
    if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0) {
        return a <= 3 || a == 5;
    }
    for (int i = 6, max = (int) Math.sqrt(a); i <= max; i = i + 6) {
        if (a % (i + 1) == 0 | a % (i + 5) == 0) {
            return false;
        }
    }
    return true;
}

public static void time(String desc, BooleanSupplier run) {
    long start = System.nanoTime();
    boolean result = run.getAsBoolean();
    if (!result)
        throw new AssertionError();
    long time = System.nanoTime() - start;
    System.out.printf("%s took %.3f mill-seconds%n", desc, time / 1e6);
}

public static void main(String... args) {
    for (int i = 2; i < 1000; i++) {
        boolean a = checkPrime(i);
        boolean b = checkPrime2(i);
        if (a != b)
            throw new AssertionError(i);
    }

    for (int i = 0; i < 3; i++) {
        time("checkPrime", () -> checkPrime(9999999998987L));
        time("checkPrime2", () -> checkPrime2(9999999998987L));
    }
}

prints

checkPrime took 26.887 mill-seconds
checkPrime2 took 13.878 mill-seconds
checkPrime took 25.527 mill-seconds
checkPrime2 took 11.286 mill-seconds
checkPrime took 16.799 mill-seconds
checkPrime2 took 9.929 mill-seconds

This is starting to get small enough that it's not clear that multiple threads would help.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130