Ytdyklly

The code below is for testing Primes.

testPrime(100000);

testPrime(1000000);

testPrime(10000000);

testPrime(100000000);

Now my goal is to make the code super fast at finding prime number, min-max, close prime.
Are there any improvements that can be done to the code below to improve the speed for IsPrime?

import java.util.ArrayList;

import java.math.*;





class Primes {





    private static long as = {2, 7, 61};



    private static long modpow(long x, long c, long m) {

        long result = 1;

        long aktpot = x;

        while (c > 0) {

            if (c % 2 == 1) {

                result = (result * aktpot) % m;

            }

            aktpot = (aktpot * aktpot) % m; 

            c /= 2;

        }

        return result;

    }



    private static boolean millerRabin(long n) {

        outer:

        for (long a : as) {

            if (a < n) {

                long s = 0;

                long d = n - 1;

                while (d % 2 == 0) {

                    s++;

                    d /= 2;

                }



                long x = modpow(a, d, n);

                if (x != 1 && x != n - 1) {

                    for (long r = 1; r < s; r++) {

                        x = (x * x) % n;

                        if (x == 1) {

                            return false;

                        }

                        if (x == n - 1) {

                            continue outer;

                        }

                    }

                    return false;

                }

            }

        }

        return true;

    }





    public static boolean IsPrime(long num) {

        if (num <= 1) {

            return false;

        } else if (num <= 3) {

            return true;

        } else if (num % 2 == 0) {

            return false;

        } else {

            return millerRabin(num);

        }

    }

    public static int primes(int min, int max) {

           ArrayList<Integer> primesList = new ArrayList<Integer>();



           for( int i=min; i<max; i++ ){

                if( IsPrime(i) ){

                   primesList.add(i);

                }

           }



           int primesArray = new int[primesList.size()];

           for(int i=0; i<primesArray.length; i++){

               primesArray[i] = (int) primesList.get(i);

           }



           return primesArray;

        }





    public static String tostring (int  arr){

        String ans="";

        for (int i=0; i<arr.length;i++){

            ans= ans+arr[i]+ " ";

        }

        return ans;

    }

     public static int closestPrime(int num) {

            int count=1;    

            for (int i=num;;i++){



                int plus=num+count, minus=num-count;

                if (IsPrime(minus)){



                    return minus;



                }



                if (IsPrime(plus)) {

                    return plus;



                }

                count=count+1;

            }

        }





    }   



//end class

You could use the Sieve of Eratosthenes for numbers less than 10 million (you are only going up to 100 million).

I think that checking the low bit (num & 1) == 0 is quicker than checking the remainder num % 2 == 0. Similarly, bit shifting is quicker for division or multiplication by 2: d /= 2 could be d >> 1.

You might experiment with doing an initial check for division by a few low primes (3, 5, 7, 11) in your IsPrime method and see if that makes a difference.

Finally, for your "random" numbers, you might want to choose products of primes, e.g. 3*5*7*11*13..., or maybe that plus 1. Maybe that's crazy. But some "random" numbers might provide richer test cases than others, and cause a faster elimination of non-primes.

Java already has BigInteger.isProbablePrime(int certainty) and BigInteger.nextProbablePrime(). (There is no method to get the previous probable prime, though, so you'll need to get creative.)

That said, your Miller-Rabin implementation works remarkably quickly and accurately. Testing numbers up to 100 million, I found that it is 100% accurate in that range. To achieve 100% accuracy in that range with BigInteger.isProbablePrime(), you would need a certainty parameter of at least 9.

To obtain a list of primes within a range, you would be better off with the Sieve of Eratosthenes. For comparison, I tried generating a list of primes up to 100 million with three methods:

• Sieve of Eratosthenes (using @JavaDeveloper's implementation with bugfixes): 3 seconds


• Your primes() function: 37 seconds


• Testing BigInteger.valueOf(i).isProbablePrime(9) for i up to 100 million: ≈ 4 minutes

In your millerRabin() function, the calculation of s and d can be factored out of the loop, as they only depend on n, not a.

Several improvements: Consider that the test "if (p % 3 == 0)..." will identify 33.3% of all numbers as composite. If Miller-Rabin takes longer than three times to test whether p % 3 == 0, adding that test makes the code run faster on average. Same obviously with p % 5 == 0 and so on. You should probably check directly at least up to 100 or so.

For a 32 bit number, you'll do about 32 squaring operations modulo p. However, you can probably do at least four by just accessing a table. For example, when a = 2 any power up to 31 can be taken from a table. That saves probably 10% or more of the work.

Sadly nobody noticed that the whole computation is broken for big numbers due to overflow in

private static long modpow(long x, long c, long m) {

    ...

    result = (result * aktpot) % m;

    ...

}

and

private static boolean millerRabin(long n) {

    ...

    x = (x * x) % n;

    ...

}

I'd suggest changing the signature of

public static boolean IsPrime(long num)

to accept int only. And obviously changing the name to isPrime.

• 
  if i<2 (one test <) is better than is if i<=1 (= test and < test)


• change String ans=""; in StringBuilder ans=new StringBuilder();


• change for (int i=0; i<arr.length;i++){ in for (int i=0,n=arr.length;i<n;i++){
  


• read Joshua Blosh "Effective Java" book