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!

Re: Need a more efficient algorithm for prime numbers.

There must be algorithms that google could find. Try that.

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.

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.