8
\$\begingroup\$

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;
        }

}


}
\$\endgroup\$
11
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ It is dangerous to use an ArrayList as a cache, as soon as the cache gets used by more than one thread. \$\endgroup\$ – Roland Illig Jun 22 '14 at 20:03
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Using a BitSet to hold the numbers is pretty efficient. I've been able to find the primes up to about 2 billion using one. This finds almost 100 million primes in well under a minute.

I can post the code if there is any interest, but I make NO claims for its quality. I also don't claim to be a good object-oriented programmer.

Using Sieve of Eratosthenes logic, you don't have to do ANY dividing. It just isn't required. I also used a BitSet to maximize how many numbers I could check.

I found that I needed a separate loop to 'sieve' out the even numbers higher than 2. The main logic just didn't work for 2.

Also, when marking out the non-primes, you only need to start at the square of the prime you just found. This is because any smaller non-prime will have already been 'sieved' out because it is divisible by a smaller prime, which you will have already found and processed. Also, your increment for the 'sieve' can be 2 times the prime you're sieving for (because the others would be even numbers, so no need to check them).

Here's my implementation:

//package Eratosthenes5;

import java.io.IOException;

import java.io.*;
import java.util.*;
//import java.lang.Math.*;
//import java.text.DecimalFormat;
//import java.awt.*;
//import javax.swing.*;

public class Eratosthenes5 {


// This uses a BitSet instead of a boolean array to see
// if this saves any memory.  It enables me to test approx.
// 8x as many numbers.  109905151 is no longer my max.
// The highest number I've reached, so far, is around 879,400,000.
//
// After giving more memory to the app, I can check for primes up
// to around 2 billion.  I've not determined the upper limit, but
// I suspect it is the java max integer size.  It finds almost 
// 100 million primes in under a minute.
// 2^31 = 2,147,483,648 


    /**
    * @param args
    * @throws IOException
    */
    public static void main(String[] args) throws IOException 
    {
        int maxSize = 1;
        int maxNumber;
        int maxSearch;
        int primeCount;
        int maxPrime;
        String name;
        name = getTheMaxNumber();
        while (name.compareTo("1") != 0) 
        {   
            long startTime = System.currentTimeMillis();
            maxSize = Integer.parseInt(name);
            maxNumber = maxSize + 1; 
            maxSearch = (int) java.lang.Math.sqrt(maxNumber);
            primeCount = 1;  //Start the count at 1 because 2 is prime and we'll start at 3
            maxPrime = -1;
            //use a BitSet array to maximize how many primes can be found
            BitSet numbList = new BitSet( maxNumber );

            numbList.set(0, maxNumber-1, true);  //set all bits to true

            numbList.clear(0);
            numbList.clear(1);

            //clear the even numbers (except 2, it's prime)
            for (long k = 4; k <= maxSize; k+=2)
            {
                numbList.clear((int)k);
            }

            // sieve out the non-primes
            for (int k = 3; k < maxSearch; k+=2)
            {   
                if (numbList.get(k))
                {   
                    sieveTheRest(k, numbList, maxSize);
                }
            }   

            //Count the primes
            for (int k = 3; k <= maxSize; k+=2)
            {   
                if (numbList.get(k))
                {   
                    maxPrime = k;
                    primeCount +=1;
                    if (primeCount % 1000000 == 0)
                    {
                        System.out.format("the " + ((primeCount/1000000 < 100) ? " " : "") 
                                                 + ((primeCount/1000000 < 10) ? " " : "")
                                                 + primeCount/1000000 + " millionth prime is: %,11d%n",maxPrime);
                    }
                }
            }

            //we're done
            System.out.format("\nMy integer from beg: %,11d%n", Integer.parseInt(name));
            System.out.format("array size         : %,11d%n", maxNumber);
    //      System.out.format("prime count        : %,11d%n", primeCount);
            System.out.format("prime count        : %,11d%n", numbList.cardinality());
            System.out.format("largest prime found: %,11d%n", maxPrime);
            System.out.format("max factor         : %,11d%n \n", maxSearch);

            long stopTime = System.currentTimeMillis();
            System.out.println("That took " + (stopTime - startTime)/1000.0 + " seconds");

            name = getTheMaxNumber();
        }//end of while 
        System.out.println("\nEnd of program");


    }//End of method Main
    /**
     * 
     * @return Passes back a string holding the maximum number to check 
     */
    static String getTheMaxNumber()
    {
        BufferedReader dataIn = new BufferedReader(new
                InputStreamReader( System.in) );
        String bigNumber = "";
        System.out.print("Please enter an integer value (1 to quit): ");
        try
        {
           bigNumber = dataIn.readLine();
        }
        catch( IOException e )
        {
           System.out.println("Error!");
        }   
        return bigNumber;

    }
    /**
    * @param myPrime   The latest prime to be found.
    * @param theBitSet The BitSet holding the prime flags
    * @param maxSize   The largest index in the BitSet
    */  
    static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize)
    {
        for (long k = myPrime*myPrime; k <= maxSize; k+=2*myPrime)
        {
            theBitSet.clear((int) k);
        }
    }

}//End of Class eratosthenes5
\$\endgroup\$
  • 3
    \$\begingroup\$ Hi, and welcome to code review. You should consider posting your code as a question, and get it reviewed. \$\endgroup\$ – rolfl Jun 22 '14 at 14:09
  • \$\begingroup\$ Well, here is my code, but I don't really have any questions about it. It works for me and I've been able to verify my results with some on-line lists of prime numbers. \$\endgroup\$ – Mark Ross Jun 22 '14 at 15:18
  • \$\begingroup\$ Thank you for the help, Jamal. I'm very new to posting and I struggle trying to figure out how to do things right. I appreciate your help and I would welcome any comments on the code. \$\endgroup\$ – Mark Ross Jun 24 '14 at 2:38
  • \$\begingroup\$ What We meant is that you should ask the code as a new question ;-) (Which I still think you should consider) \$\endgroup\$ – rolfl Jun 24 '14 at 2:42
  • \$\begingroup\$ Ok, I posted the code under a separate question. Feels a bit redundant, though. \$\endgroup\$ – Mark Ross Jun 24 '14 at 6:48
1
\$\begingroup\$

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number - not every smaller number. This is the siev of Eratosthenes in the form of an array but not only for 2, 3 and five, but every prime number. In fact you only need to check against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {

    int index, candidate;

    int[] primes = new int[targetNumberOfPrimes];

    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
}

It took my computer about 0.7 seconds for 40000 prime numbers.

\$\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.