# Need a more efficient algorithm for prime numbers.

• September 29th, 2012, 11:47 AM
firstTimeJava
Need a more efficient algorithm for prime numbers.
Here is my current algorithm, the TimeExec is just a class to print out how long it takes to run the code:

Code java:

```public class Primes {   /** * Get a set of prime numbers. * @param no the number of primes to create * @return an array containing the requested number * of primes */ public static int[] getPrimes(int no) { int[] primes = new int[no]; int primeInx = 0; int i = 2;   if (primeInx < no) { primes[primeInx++] = 1; }   while (primeInx < no) { boolean prime = true; for (int j = 2; j < i; j++) {   if (i == i / j * j) { prime = false; } } if (prime) { primes[primeInx++] = i; } i++; }   return primes; }   public static void main(String[] args) { new TimeExec(new Runnable() { public void run() { int[] primes = getPrimes(1000); } }, "Get 1,000 primes", System.out).start();   //the 10,000 primes took the library's lab comp 19.125s new TimeExec(new Runnable() { public void run() { int[] primes = getPrimes(10000); } }, "Get 10,000 primes", System.out).start();   new TimeExec(new Runnable() { public void run() { int[] primes = getPrimes(100000); } }, "Get 100,000 primes", System.out).start();   // new TimeExec(new Runnable() { // public void run() { // int[] primes = getPrimes(1000000); // } // }, "Get 1,000,000 primes", System.out).start(); } }```

I need to get it to be able to print out the 1,000,000 primes fairly quickly. Any help would be awesome, thank you!
• September 29th, 2012, 11:54 AM
Norm
Re: Need a more efficient algorithm for prime numbers.
There must be algorithms that google could find. Try that.
• September 29th, 2012, 12:46 PM
helloworld922
Re: Need a more efficient algorithm for prime numbers.
Try using a sieve. These are more memory intensive but they're very fast at finding prime numbers less than x.

For something fairly simple see Wikipedia: Sieve of Eratosthenese.

A little bit of self-promotion, but for moderately heavy prime generation (basically an optimized Sieve of Eratosthenes with a small hand-coded wheel factorization), see Optimizing the Sieve of Eratosthenes.

And for your balls-out bonkers version, see Prime Sieve, which I think is the current record holder for consecutive prime number generation. From what I can tell it's a multi-threaded Sieve of Eratosthenes with advanced wheel factorization. Unfortunately it's implemented in C++, not Java.
• November 16th, 2012, 10:15 PM
aesguitar
Re: Need a more efficient algorithm for prime numbers.
Sieves work great for finding lists of primes up to n, much faster than the method you are currently using (for a list of primes to 1000000, sieving returns the list in 64ms on my machine, while brute force returns it in 643 ms). However, I can give you some pointers if you want with your currents algorithm:

Code java:

```for (int j = 2; j < i; j++) {   if (i == i / j * j) { prime = false; } }```

First, you upper bound is way to high. j need only go to the square root of i to check all possible factors. Also

Code java:

```if (i == i / j * j) { prime = false; }```

can be changed to

Code java:

```if (i % j == 0) { prime = false; }```

That percent sign thingy is called a modulo. What it does is it, in this case, divides i by j and returns the remainder. So, for example, 7 % 2 = 1 because when you long divide, you get 3 remainder 1 or simply 3 and 1/2. If i evenly divides into j, then it will always be zero, if not, then it will be some integer > 0.

One other thing with building the list your way, using the ArrayList class will be much, much easier than using that array.