Primes Tester for speed performance

Question

I was given a homework assignment in Java to create classes that find Prime number and etc (you will see in code better).

class Primes {

    public static boolean IsPrime(long num) {
        if (num%2==0){
            return false;
        }

        for (int i=3; i*i<=num;i+=2) {
            if (num%i==0) {
                return false;    
            }
        }
        return true;
    }    //    End boolen IsPrime

    public static int[] primes(int min, int max){
        int counter=0;
        int arcount=0;

        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                counter++;
            }    
        }

        int [] arr= new int[counter];
        for (int i=min;i<max;i++){
            if (IsPrime(i)){
                arr[arcount]=i;
                arcount++;
            }                
        }
        return arr;
    }    //    End Primes

    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(long num){
        long e = 0 , d = 0 , f = num;
        for (int i = 2; i <= num + 1 ; i++){
            if ((num + 1) % i == 0){
                if ((num + 1) % i == 0 && (num + 1) == i){
                    d = num + 1;
                    break;
                }
                num++;
                i = 1;
            }
        }
        num = f;
        for (int i = 2; i < num; i++){
            if ((num - 1) % i == 0){
                if ((num - 1) % i == 0 && (num - 1) == i){
                    e = num - 1;
                    break;
                }
                num--;
                i = 1;
            }
        }
        num = f;
        if (d - num < num - e) System.out.println("Closest Prime: "+d);
        else System.out.println("Closest Prime: "+e);

        return (int) num;
    }     //    End closestPrime

}//end class

The goal of my code is to be faster (and correct). I'm having difficulties achieving this. Suggestions?

class Primes {

     public static boolean IsPrime(int num) {


         if (num==1){
             return false;
         }
         for (int i=2; i<Math.sqrt(num);i++) {
             if (num%i==0) {
                 return false;
             }
         }
         return true;
     }
          //  End boolen IsPrime


     public static int[] primes(int min, int max){
         int size=0;
         int [] arrtemp= new int[max-min];

         for (int i=min;i<max;i++){
             if (IsPrime(i)){
                 arrtemp[size]=i;
                 size++;
             }   
         }

         int [] arr= new int[size];
         for (int i=0;i<size;i++){
                arr[i]=arrtemp[i];

             } 
         return arr;

     }  


    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 closestPrime

}//end class

I think you can improve this code a bit:

Test Code:

/**
Ex2: Overall time: 2545  m-sec
*/

public class PrimesTester {
    public static void main(String[] args){
        long t1 = new Date().getTime();  // primes
        testPrime(100000);
        testPrime(1000000);
        testPrime(10000000);
        testPrime(100000000);
        long t2 = new Date().getTime();
        System.out.println("Ex2: Overall time: "+(t2-t1)+"  m-sec"); 
    }

    public static void testPrime(int num) {    
        System.out.println();
        System.out.println("***** Testing class Primes for: "+num+"*****");
        int  min= num, max = min+min/2;

        long t1 = new Date().getTime();  // primes
        int[] primes = Primes.primes(min,max);
        long t2 = new Date().getTime();
        long p10_6 = Primes.closestPrime(min);
        long t3 = new Date().getTime();

        System.out.println("Ex2: prime test, time: "+(t2-t1)+"  m-sec , number of primes: "+primes.length);
        System.out.println("Ex2: closestPrime test, time: "+(t3-t2)+"  m-sec , prime: "+p10_6);
    }
}

Answer 1

The goal of my code is to be faster (and correct). I'm having difficulties achieving this. Suggestions?

This is a neverending task. My suggestion is to stop performance improvements without a goal. To test the correctness, you should write unit tests.

To explain this a little bit more: There are some advanced algorithms, like sieves, deterministic prime tests, and so on. They depend on the fact that you have to know them or that you have the math background.
One of the questions is the expected input. Depending on the input, the algorithm can be optimized.
An other approach would be trading computations against memory. You could precalculate all primes and store them inside the class.
An other question is the architecture of the platform, depending on the virtual machine and the platform, there could be different techniques.
You could use a native call, to do it in c or assembler.
And so on, there is no end.

---

Some obvious things from your code:

Use a code convention, best practice would be the java code convention from sun/oracle.
And, as already said, avoid abbreviations.

---

long t1 = new Date().getTime();  // primes

If you want to measure the distance between two moments, use System.currentTimeMillis().

---

for (int i=2; i<Math.sqrt(num);i++)

This will most probably calculate the sqrt for every iteration. sqrt is one the more expensive operations. Do it once and save the result in a variable.
And you do not need to test all divisors. You do not have to test with numbers, which are known not to be prime (This means, you do not have to test with any number 2*n, n>1. Only with numbers 2*n + 1, n>0. Or only with numbers 6n +- 1, n > 0. Or any similar approach around the local minimums of the euler phi function)

---

     int [] arr= new int[size];
     for (int i=0;i<size;i++){
            arr[i]=arrtemp[i];

         } 

To copy an array, you can use System.arraycopy(...).

---

for (int i=min;i<max;i++){
         if (IsPrime(i)){
             arrtemp[size]=i;
             size++;
         }   
     }

To find all primes, you could use the sieve of Eratosthenes, which is one of the fastest ways inside the java integer range.

---

int [] arrtemp= new int[max-min];

To reduce memory usage, increase locality and help the caches, you could use a BitSet. A custom, handmade implementation would be more efficient than the one found inside the java library.

---

public static boolean IsPrime(long num) {
    ....
}

You could use a deterministic Miller-Rabin test here.

Answer 2

Your IsPrime method looks already pretty good to me, just one little thing there in the line:

if (num % 2 == 0) {
     return false;
}

It would return falsefor num=2, but 2is also a prime number. So just in case I would add:

if(num==2){
   return true;   // the first prime number is 2
}
if( num%2==0 || num<2){
   return false;  // numbers smaller than 2 (also negative numbers) can't be primes
}

In you primes method you are checking all possible numbers from minto max, now you said it was a homework so I don't know if you are supposed to use this, but instead of an array you can use a ArrayList. The ArrayListcan hold Integer (! not int, thats a little different) and it will change it's size dynamically. Like this:

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);
        }
   }
   // after you found all primes, copy the results in an array, that can be returned
   int[] primesArray = new int[primesList.size()];
   for(int i=0; i<primesArray.length; i++){
       primesArray[i] = (int) primesList.get(i);
   }

   return primesArray;
}

True, this doesn't look much better. But as you can see you don't have to set a size to the ArrayList when initializing it. In your original code you have two loops, each checking if the loop index is a prime. Each prime check is again a loop with up to n/2 steps. So if you are checking m numbers you may end up with 2*m*(n/2) operations.

In my version you also have two loops, but you only have to check ones for primes. So you have n/2 steps to check for primes and then again primes.length steps to copy the result in an array. And the number of found primes will be much smaller than n/2 so, all in all, this method has way less than m*(n/2) operations (best case even exactly m*(n/2))

In your fourth method closestPrime you are actually reusing your prime-finding algorithm to check all numbers that are smaller or greater than num. Now I can't tell you which one is faster, but it is definitely easier to just reuse your isPrime method, to check the closest prime to num. When you already have a method that does a good job, reuse it!

Now you didn't ask for it, but if I may give you a few tips for code style:

• methods (and variables) should begin with a small letter. It serves nothing else but easier understanding the code.
• avoid unreadable variable names. Now you know what ans or arcount stands for, but in a few weeks it gets harder to understand. Just say arrayCounter and you always know what it means
• you may declare variables like this : int e=0, f=2,... but thats nothing else than int e=0; int f=2; ... and after almost 12 years of Java I can tell you the second version is way easier to keep track of you code.

That's it, I hope I could help a little bit

Answer 3

In a comment I made the point that caching is good. Here is an implementation CachingPrimes that showes some performance improvements:

class CachingPrimes {
    private static ArrayList<Long> cache = new ArrayList<Long>();
    // start with two primes. The last prime has to be an odd number
    static { cache.add((long) 2); cache.add((long) 3); }

    // largest prime is at least upTo
    public static void expandCache(long upTo) {
        long last = cache.get(cache.size() - 1);
        if (last >= upTo) return;
        for (long candidate = last; candidate <= upTo; candidate += 2) {
            for(;; candidate += 2) {
                if (isPrime(candidate)) {
                    cache.add(candidate);
                    break;
                }
            }
        }
    }

    public static boolean isPrime(long num) {
        if (num == 2     ) return true;
        if (num <  2     ) return false;
        if (num %  2 == 0) return false;

        long upperBound = (long) Math.sqrt(num); // bug
        expandCache(upperBound);

        for (long prime : cache) {
            if (prime > upperBound) break;
            if (num % prime == 0)   return false;
        }
        return true;
    }

    public static long[] primes(long min, long max) {
        expandCache(max);
        int start = 0;
        int count = 0;
        for(long prime : cache) {
            if (prime < min) start++;
            if (min <= prime && prime <= max) count++;
        }
        long[] out = new long[count];
        for (count--; count >= 0; count--) {
            out[count] = cache.get(start + count);
        }
        return out;
    }

    public static long closestPrime(long num) {
        expandCache(num);
        long smaller = 0, larger = 0;
        for (long prime : cache) {
            if (prime < num)  smaller = prime;
            if (prime == num) return prime;
            if (prime > num) {
                larger = prime;
                break;
            }
        }
        long
            smaller_d = num - smaller,
            larger_d  = larger - num;
        long nearest = (smaller_d <= larger_d) ? smaller : larger;
        System.out.println("Closest prime: " + nearest);
        return nearest;
    }
}

I compared the speed of this implementation to your (original) code (with all numbers that could be primes changed to long).

    testPrime(100000);    // very small difference between implementations
    testPrime(1000000);   // I'm twice as fast
    testPrime(10000000);  // I'm 2–3 times as fast
    testPrime(100000000); // not tested

As you can see, my code isn't especially optimized. Using a different data structure from ArrayList could bring a speedup. Loops could be optimized. My code also has a bug: upperBound = (long) Math.sqrt(num) squared may be smaller than num. Some correction like while (upperBound * upperBound < num) upperBound++; would be one solution that provides an exact value for upperBound. square = upperBound * upperBound; if (square < num) upperBound += num - square; should be faster, but is very inexact.