Prime Tester for speed

Question

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

My code:

    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?

**New code:

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 did try to make it a bit better. what do you think, it can be improved more? (the speed test is still high...)

Answer 1

In your primes function you:

• Check if the current number is divisible by two
• Check to see if it's prime
• Create an array to put your output in.
• Check every number in the range again for primality before putting it in your array.

The problem is in the last step. By double-checking whether each number is prime, you're duplicating your most expensive operations.

You could use a dynamic data structure and add prime numbers to it as you find them. That way you only need to check once.

Alternatively, you could create a boolean array which is the size of your input range. Then as you find primes, set the corresponding array value to true.

UPDATE:

There are still a number of improvements you can make, but some will require more work than others to implement. Look at the specifics of your test and see what fits your needs.

Low-hanging fruit:

• Use an ArrayList to collect primes as you find them in primes, as opposed to looping over the values twice.
• In closestPrime, you're checking every single value on either side of num: half of these are even, thus not prime. You could adapt your code to check only odd numbers for primality.

Trickier to implement:

• Try a more advanced algorithm for IsPrime: check out the Sieve of Eratosthenes

Above all, you should spend some time figuring out exactly where the bottlenecks are in your code. Oftentimes performance problems are caused by code we thought was perfectly fine. You might consider looking into the code-profiling options available in your development environment.

Answer 2

I see a couple problems with your answer. First, 2 is a prime number. Your first conditional in IsPrime breaks this. Second, in your primes method, you are cycling through all number from min to max. You can safely ignore all negative numbers and all even numbers (as you do in IsPrime). It would make more sense to combine these two methods and save all the extra cycles.

Answer 3

You make quite a few calls to isPrime(), each of which is very expensive. Your first step should be to minimize the number of times you do that, since the result doesn't change for any given number, there's no point calling more than once. You can do this with memoization by storing the values once they're computed:

ArrayList<Integer> memoList = new ArrayList<Integer>();
for(int i = 0; i < max; i++) {
  if(isPrime(i)) {
    memoList.add(i);
  }
}

Now memoList holds all the primes you need, up to max, and you can loop over them rapidly without needing to recompute them every time.

Secondly, you can improve your isPrime() method. Your solution loops over every odd number from 3 to sqrt(n), but why not just loop over the primes, now that we know them?

public static boolean IsPrime(long num) {
    for(int p : memoList) {
        if(num % p == 0) {
            return false;
        }
    }
    return true;
}

These changes should dramatically improve how quickly your code runs, but there has been a lot of research into even more efficient ways of calculating primes. The Wikipedia page on Prime Numbers has some very good information on further tactics (prime sieves, in particular) you can experiment with.

Remember that as this is homework you should be sure to cite this page when you turn it in. You're welcome to use and expand upon this code, but not citing this question and any other resources you use is plagiarism.