Checking if an int is prime more efficiently

Question

I recently was part of a small java programming competition at my school. My partner and I have just finished our first pure oop class and most of the questions were out of our league so we settled on this one (and I am paraphrasing somewhat): "given an input integer n return the next int that is prime and its reverse is also prime for example if n = 18 your program should print 31" because 31 and 13 are both prime. Your .class file would then have a test case of all the possible numbers from 1-2,000,000,000 passed to it and it had to return the correct answer within 10 seconds to be considered valid.

We found a solution but with larger test cases it would take longer than 10 seconds. I am fairly certain there is a way to move the range of looping from n,..2,000,000,000 down as the likely hood of needing to loop that far when n is a low number is small, but either way we broke the loop when a number is prime under both conditions is found. At first we were looping from 2,..n no matter how large it was then i remembered the rule about only looping to the square root of n. Any suggestions on how to make my program more efficient? I have had no classes dealing with complexity analysis of algorithms. Here is our attempt.

public class P3
{

   public static void main(String[] args){

    long loop = 2000000000;
    long n = Integer.parseInt(args[0]);
    for(long i = n; i<loop; i++)
    {
      String s = i +"";
      String r = "";
      for(int j = s.length()-1; j>=0; j--)
        r = r + s.charAt(j);
      if(prime(i) && prime(Long.parseLong(r)))
      {
          System.out.println(i);
          break;
      }
    }
    System.out.println("#");
  }

  public static boolean prime(long p){


for(int i = 2; i<(int)Math.sqrt(p); i++)
    {
      if(p%i==0)
        return false;
    }
    return true;
  }
}

ps sorry if i did the formatting for code wrong this is my first time posting here. Also the output had to have a '#' after each line thats what the line after the loop is about Thanks for any help you guys offer!!!

Answer 1

It seems like you are incrementing by 1, but you should be incrementing by 2. No even number is prime but 2.

Answer 2

First you should precompute all prime numbers up to 2,000,000,000 using something like the Sieve of Eratosthenes. You can store whether each number is prime in a bit array.

This is pretty fast, and then checking each individual number for primality is a simple lookup.

If you can't do this because you need to run a new instance of your program for each test case, use a fast primality testing algorithm like Miller-Rabin.

Answer 3

The big inefficiency here is your prime testing method prime. Take a think about the number of times it will have to test the very same numbers, and concentrate on how one might take advantage of memory structures in order to avoid some of the repeated calculations.

Answer 4

Your prime check is very inefficient. In fact, you don't need to re-check multiples of already checked numbers. So when you check for %2, you don't need to check for %4.

To find out whether a number is a prime, you only have to try to divide it by all known primes until you reach the square root of the number to be checked. Doing this reduces the number of divisions vastly: if your app has a list of the primes from 2..~44721 (for instance computed as preparation step), you can check all numbers until 2000000000 pretty quickly.

Also, you should make sure to check the smaller of the two permutations first (e.g. in your sample first check 13, then 31).

Edit:

Here's a sample I quickly put together in C# (you'll need to do some minor syntactic changes to have it run on Java, but I just had a C# compiler at hand):

public static long reverse(long value) {
    long result = 0;
    while (value > 0) {
        result = result*10+(value%10);
        value /= 10;
    }
    return result;
}

public static long[] knownPrimes = new long[1000000];
public static int knownPrimeCount = 0;

public static bool isPrime(long value) {
    // we loop through all already known primes and try to divide by those (sieve sort of)
    for (int primeIndex = 0; primeIndex < knownPrimeCount; primeIndex++) {
        long primeToCheck = knownPrimes[primeIndex];
        if (value % knownPrimes[primeIndex] == 0) {
            // can be divided by the given prime -> not a prime
            return false;
        }
        if ((primeToCheck * primeToCheck) > value) {
            // square exceeds the value -> is a prime, no more checks needed
            return true;
        }
    }
    // if we come here, we've run out of primes to check against, and therefore we should indicate this as error
    throw new ArgumentException(string.Format("{0} is too large to be checked against known primes", value), "value");
}

public static void Main(String[] args){
    long loop = 2000000000;
    long n =    1999990000;

    // first we initialize all the primes we may be needing for the final computation
    knownPrimes[knownPrimeCount++] = 2;
    for (long i = 3; true; i++) {
        if (isPrime(i)) {
            // store the new prime
            knownPrimes[knownPrimeCount++] = i;
            if ((i * i) > loop) {
                break; // we have all the primes we need now
            }
        }
    }

    // now we try to find matches
    for (long i = n; i <= loop; i++) {
        long reversed = reverse(i);
        if ((reversed <= i) && isPrime(reversed) && isPrime(i)) {
            Console.WriteLine("{0} <-> {1}", i, reversed);
        }
    }
    Console.WriteLine("#");
    Console.ReadKey(true);
}

On my computer and with the given loop and n in the source the result shows up instantaneous.

Answer 5

Using BigInteger.isProbablePrime(certainty) and BigInteger.nextProbablePrime() can significantly cut down the number of cases you need to check quite efficiently

Answer 6

I havent done this before, but here are some things that come to my mind.

if your squareroot is a integer it the number is not prime

if the number ends in a 0,2,4,5,6, or 8 it is not prime /except 2 itself

Number can be divided by 3 if the sum ofdigits is divisible by 3 and by 9 if sum is 9.

I dont know wether testing for this things help you, at least the test of the squareRoot should help because you have to compute it anyway and you can be done already.

Oh and ofcourse your efficence will increase a lot if you do something like Miller–Rabin primality test http://en.wikipedia.org/wiki/Miller-Rabin_primality_test. Your actual test only needs to be done in the cases that arent certain.

Answer 7

Another speed improvement you can make in main is to change your loop to pre-filter some composite numbers, unrolling some iterations into a sequence of tests. The simplest is to test 2 outside the loop, then test odd numbers (2*i+1). Slightly more complex is to test 2, 3, then 6*i ± 1. You can keep extending this approach, testing the first n primes, then looping oven pn# * i+j, where p_n# is the prime primordial (the product of the first n primes) and j is a positive integer less than and coprime to p_n#.

To speed up the prime method, you could start with a fast probabilistic prime test and test using a slower deterministic test only for those cases the probabilistic test can't determine.

Answer 8

Even faster than all of that is using the Miller-Rabin test. It's a probabilistic test, and therefore has a certain level of error; however, the test multiple times shrinks that error as small as needed (50 often suffices for commercial applications).

Not in Java, but here's a quick implementation in Python I cooked up.

Answer 9

@outis...i see what you are saying thats a neat little trick i must say. thank you for that.

@Graham...also cool i read an article on the test you mentioned because although I think i understood the gist of it from the comments you made Python always looks like greek to me. I know everyone says its one of the simpler languages to pick up but for whatever reason java and c++ always look more readable to me. Anyway, yea that wouldve been a much better way to do it. Thanks again to all of you who gave me tips I learned alot from this board. Can't for my data structures and algorithms class in the fall!!!

Answer 10

The easiest option would be use use an existing big integer library. It won't have bugs, and it will provide all the supporting functions.

If you are writing your own implementation (i.e. for an assignment), I'd recommend working from a pseudo code algorithm in a book so that you understand what you are doing.

That being said, one of the simplest methods is to use Jacobi and Legendre, and compare for equality. I just submitted an assignment for RSA encryption. Here is what I did for single precision, however the algorithms are general and work for multiple precision integers too.

typedef uint64_t BigIntT;
typedef int64_t SBigIntT;

// This function calculations the power of b^e mod phi
// As long as 
//      b*b is smaller than max(BigIntT) 
//      b*phi is smaller than max(BigIntT)
// we will not have overflow.
BigIntT calculatePower (BigIntT b, BigIntT e, BigIntT m) {
    BigIntT result = 1;

    while (e != 0) {
        if (e & 1) {
            result = (result * b) % m;
        }

        e = e >> 1;
        b = (b * b) % m;
    }

    return result;
}

// This function implements simple jacobi test.
// We can expect compiler to perform tail-call optimisation.
SBigIntT jacobi (SBigIntT a, SBigIntT b) {
    if (a == 0 || a == 1) {
        return a;
    } else if (a % 2 == 0) {
        if (((b*b - 1) / 8) % 2 == 0) {
            return jacobi(a/2, b);
        } else {
            return -jacobi(a/2, b);
        }
    } else if ((((a-1) * (b-1)) / 4) % 2 == 0) {
        return jacobi(b % a, a);
    } else {
        return -jacobi(b % a, a);
    }
}

// This function implements : http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test
bool testPrime (BigIntT p) {
    int tests = 10;

    if (p == 2) {
        return true;
    }

    while (tests-- > 0) {
        BigIntT a = generateRandomNumber(2, p);

        if (greatestCommonDivisor(a, p) == 1) {
            BigIntT l = calculatePower(a, (p-1)/2, p);
            SBigIntT j = jacobi(a, p);

            // j % p == l
            if ((j == -1) && (l == p-1) || (j == l)) {
                // So far so good...
            } else {
                // p is composite
                return false;
            }
        } else {
            // p is composite
            return false;
        }
    }

    return true;
}

Performance is very good even with large numbers.

Answer 11

@David get the square root of a number and then loop till square root eliminate even numbers and see if it is not divisble