current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite
1

The question asked to find all the prime numbers within a particular range. The way I approached this was to loop through each of the numbers within the range and for each number check whether it's a prime. My method for checking prime is to start at 3 and loop till number/2 in hops of 2(essentially excluding all the even numbers). Can somebody take a look at the code an tell me how I might be able to better this snippet and what are some of the aspects that I am missing.

public class PrimeBetween{

public static void main(String[] args){
        printAllPrimes(Integer.parseInt(args[0]),Integer.parseInt(args[1]));
}

public static void printAllPrimes(int start,int end){
        for(int i = start;i <= end;i++){
                if(isPrime(i))
                        System.out.println("Print prime:"+i);
        }

}

private static boolean isPrime(int i){
        if(i%2 == 0 && i!=2)
                return false;
        else{
                if(i == 1) return false;
                for(int p=3;p<=i/2;p+=2){
                        if(i%p == 0)
                                return false;
                }
                return true;
        }

}


}

Thanks

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

Well, for starters, it is a proven mathematical fact that if a number is prime, it is not divisible by any prime number that is less than its square root. In your inner loop you go up to i/2 and you can change this to Math.floor(Math.sqrt(i)).

Because you are checking for a range of numbers, you would probably benefit from a cache of primes, rather than testing every odd number less than the square root.

Something like this:

package mypackage;

import java.util.ArrayList;

/**
 * Checks for primeness using a cache.
 */
public class PrimeCache {

    private static ArrayList<Integer> cache = null;

    static {
        cache = new ArrayList<Integer>();
        cache.add(2);
    }

    public static boolean isPrime(int i) {
        if (i == 1) return false; // by definition

        int limit = (int) Math.floor(Math.sqrt(i));
        populateCache(limit);

        return doTest(i, limit);
    }

    private static void populateCache(int limit) {
        int start = cache.get(cache.size() - 1) + 1;
        for (int i = start; i <= limit; i++) {
            if (simpleTest(i)) cache.add(i);
        }
    }

    private static boolean simpleTest(int i) {
        int limit = (int) Math.floor(Math.sqrt(i));

        return doTest(i, limit);
    }

    private static boolean doTest(int i, int limit) {
        int counter = 0;
        while (counter < cache.size() && cache.get(counter) <= limit) {
            if (i % cache.get(counter) == 0) return false;
            counter++;
        }

        return true;
    }
}
share|improve this answer
 
This pretty great. Thanks. –  sc_ray Apr 12 '12 at 17:15
add comment
up vote 2 down vote

You could also use the sieve of Eratosthenes so as to improve time complexity. It has a lot of optimizations, you can even reduce the memory footprint by using bit operations, and many others, if you're into maths.

share|improve this answer
add comment
up vote 2 down vote

Based on the feedback given by Donald.McLean and Grewe Kokkor, I have rewritten the prime-generation as follows:

    public class PrimeBetweenRevised{

    public static void main(String[] args){

    int firstInt = Integer.parseInt(args[0]);
    int lastInt = Integer.parseInt(args[1]);

    BitSet allPrimes = GenerateAllPrimes(lastInt);
    GetAllPrimesInBetween(firstInt,lastInt,allPrimes);

    }

    private static void GetAllPrimesInBetween(int a,int b,BitSet primes){
            for(int i=a;i<=b;i++){
                    if(primes.get(i))
                            System.out.println(i);
            }
    }

    private static BitSet GenerateAllPrimes(int upperbound){
            BitSet primeSet = new BitSet();
            for(int i=2;i<=upperbound;i++){
                    primeSet.set(i);
            }

            for(int i = 2;i<=upperbound;i++){
                    int start = 2*i;
                    int current = i;
                    for(int j = start;j<=upperbound;j+=current){
                            primeSet.clear(j);
                    }
            }
            return primeSet;
    }
}
share|improve this answer
add comment
up vote 0 down vote

i think this code will be much faster for isPrime:

private static boolean isPrime(int i) {
        if(i <= 1 ) return false;
        if(i == 2 ) return true;
        //test for all multiples of 2
        if ((i & 1 ) == 0) return false;

        //test for all multiples of 3
        if ((i %3 ) == 0) return false;
 //other wise test all odd numbers, but we are checking only for probable prime numbers of the
// form 6K+1/6K-1 k>1;

        for(int j=6; (j*j)<=i; j+=6) {
            if(i%(j-1)==0)
                return false;
            if(i%(j+1)==0)
                return false;
        }
        return true;
    }
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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