1
\$\begingroup\$

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);
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Hello and Welcome to Programmers. This question is off-topic here but on topic for Stack Overflow (if it's broken) and Code Review (if it's not and you just want to make it better) Which do you want me to move it to? Have a pleasant day. \$\endgroup\$
    – user7402
    Mar 26, 2013 at 2:16
  • \$\begingroup\$ @WorldEngineer Hi, tnx for quick answer, i need to improve this code. feel free to move it to the right place. (i think Code Review will do the trick) \$\endgroup\$
    – Alaev
    Mar 26, 2013 at 2:20

3 Answers 3

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ i think i get your point, but some how i don't understand how to execute it in to my code. so the IsPrime will save all the primes that it find in to array, and for me to find a way to reuse IsPrime again.. \$\endgroup\$
    – Alaev
    Mar 26, 2013 at 21:43
2
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Hi, thx for the answer i think i got your point. what do you think about the second one? do you think it can be improved more? \$\endgroup\$
    – Alaev
    Mar 26, 2013 at 13:06
  • \$\begingroup\$ Looks pretty much improved to me. The Math.sqrt is a really good idea. Just make sure you check for negative inputs in the IsPrime() because primes can only be natural numbers. I am not sure if there is a case where closestPrimewill actually try a negative number, but just in case. Just out of interest: what should happen when closestPrime is called with a prime as argument? Now you could run some tests and print out the calculation time (`long start= System.currentTimeMillis(); (... do calculation...) System.out.println("time="+(System.currentTimeMillis()-start)); \$\endgroup\$
    – GameDroids
    Mar 26, 2013 at 13:48
  • \$\begingroup\$ Yes, the goal of this code its to be tested in the code that i just added. but i just cant get better result then 2545 m-sec... my code test out 200,000 m-sec... any idea how i can achieve better result? \$\endgroup\$
    – Alaev
    Mar 26, 2013 at 14:58
  • \$\begingroup\$ Making the primeList a static member of the class would allow isPrime to leverage existing lists of primes (only test against divisibility by primes, not by every even number). This might yield a speedup. Calculating the nearest prime would get faster as well, if the cache already holds numbers up to that region. If you take enough care, you can even parallelize prime tests. \$\endgroup\$
    – amon
    Mar 26, 2013 at 15:50
  • \$\begingroup\$ I don't see any ways for improvement. It's all in the IsPrime method now. I only see a way to make the code shorter in your closestPrime(): for(int i=0;i<num;i++){ if (IsPrime(num-i)){ return num-i; } if (IsPrime(num+i)) { return num+i; } } But you don't really save many operations with this. Well you could check if numis an even number and iterate through odd numbers like: for(int i=(num%2==0?1:0); i<num;i+=2){...} or something like that \$\endgroup\$
    – GameDroids
    Mar 26, 2013 at 15:51
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.