# Thread: More Efficient Prime Searching Algorithm?

1. Member
Join Date
Jun 2012
Posts
1
Rep Power
0

## More Efficient Prime Searching Algorithm?

I started working on some Project Euler problems today, and I'm having problems with the one that seeks the sum of all prime number less than 2000000.
It's running very slowly, so I was wondering if there existed a faster prime searching algorithm than the one I have now. (It's currently some sort of inefficient prime sieve.)
Here is the code:
Java Code:
```public class Problem10 {

public static void main(String args[]){

int sum = 0;

boolean[] a = primesList();

for(int i = 0; i<1999999; i++){

if(!a[i]) sum+=i+2;

}

System.out.println(sum);

}

public static boolean[] primesList(){

boolean[] a = new boolean[1999999];
for(int i = 0; i<1999999; i++){

if(!a[i]){

int j = i+2;
for(int k = i+3; k<2000001; k++){

if(divTest(k, j)) a[k-2]=true;

}

}
if(i%10000==0) System.out.println(i);
}

return a;

}

public static boolean divTest(int i, int j){

boolean b = false;
if (i/j==((double) i)/j) b=true;
return b;

}

}```

2. ## Re: More Efficient Prime Searching Algorithm?

For a sieve you don't need to divide anything; for all multiples of 2 (except 2 itself) clear the corresponding flag. Check the first next number with its flag set, say x; clear all multiples of x (except x itself) and repeat the process until done. While checking for those numbers with their flag set in the outer iteration, you might as well add them to a total value; that way, when you're done with your sieve you're done with your entire algorithm.

kind regards,

Jos

3. Banned
Join Date
Jun 2012
Location
Beijing,China
Posts
34
Rep Power
0

## Re: More Efficient Prime Searching Algorithm?

Yes. there are some more efficient way.
Did you search it at Wiki . PRIME NUMBER

for (int i=1;i < sqrt(2000000);i++ )
for (int j=1;j <=2000000;j++)
if a[j]= multiplies of i then call missing a[j]

Ksharp

4. ## Re: More Efficient Prime Searching Algorithm?

That isn't very efficient; better try an ordinary sieve:

Java Code:
```		boolean[] b= new boolean[100000];

b[0]= b[1]= true;

for (int x= 2; x < b.length; x++)
if (!b[x])
for (int y= x+x; y < b.length; y+= x)
b[y]= true;```
if b[x] is true x is not a prime number.

kind regards,

Jos

5. Senior Member
Join Date
Mar 2009
Posts
552
Rep Power
12

## Re: More Efficient Prime Searching Algorithm?

Originally Posted by JosAH
Java Code:
```boolean[] b= new boolean[100000];

b[0]= b[1]= true;

for (int x= 2; x < b.length; x++)
if (!b[x])
for (int y= x+x; y < b.length; y+= x)
b[y]= true;```
Wouldn't it be more efficient to only check for values of x up to b.length/2? It seems a bit ridiculous to be incrementing x when x+x will always be greater than or equal to b.length, so the inner for loop will never execute once x > b.length/2.

So instead of what josAH posted, unless I'm missing something, this would end faster, if not by much for tests up to less than a million or so:
Java Code:
```boolean[] b= new boolean[100000];

b[0]= b[1]= true;
for (int x= 2; x < b.length/2; x++)
if (!b[x])
for (int y= x+x; y < b.length; y+= x)
b[y]= true;```

6. ## Re: More Efficient Prime Searching Algorithm?

Originally Posted by Singing Boyo
Wouldn't it be more efficient to only check for values of x up to b.length/2? It seems a bit ridiculous to be incrementing x when x+x will always be greater than or equal to b.length, so the inner for loop will never execute once x > b.length/2.

So instead of what josAH posted, unless I'm missing something, this would end faster, if not by much for tests up to less than a million or so:
Java Code:
```boolean[] b= new boolean[100000];

b[0]= b[1]= true;
for (int x= 2; x < b.length/2; x++)
if (!b[x])
for (int y= x+x; y < b.length; y+= x)
b[y]= true;```
It is, indeed, a bit more efficient, i.e. for the last half (here 500,000) nothing needs to be done and the inner loop doesn't execute; but for the first half many more iterations have been made; 1e6/2+1e6/3+1e6/4 ...

kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•