Results 1 to 6 of 6
 06252012, 05:41 AM #1Member
 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[k2]=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; } }
 06252012, 08:00 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,516
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06252012, 10:18 AM #3Banned
 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
 06252012, 10:46 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,516
 Blog Entries
 7
 Rep Power
 20
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;
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
 06272012, 10:26 AM #5Senior Member
 Join Date
 Mar 2009
 Posts
 552
 Rep Power
 6
Re: More Efficient Prime Searching Algorithm?
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;
If the above doesn't make sense to you, ignore it, but remember it  might be useful!
And if you just randomly taught yourself to program, well... you're just like me!
 06272012, 11:42 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,516
 Blog Entries
 7
 Rep Power
 20
Re: More Efficient Prime Searching Algorithm?
cenosillicaphobia: the fear for an empty beer glass
Similar Threads

Big prime
By diamonddragon in forum New To JavaReplies: 25Last Post: 02022012, 11:04 PM 
Palindromic Prime?
By soccergirl67 in forum New To JavaReplies: 5Last Post: 12012011, 09:48 AM 
Prime Number  System print all the prime numbers ...
By pinkdreammsss in forum New To JavaReplies: 20Last Post: 04262009, 01:50 AM 
Prime numbers
By tercius in forum New To JavaReplies: 3Last Post: 05042008, 06:05 AM 
Prime numbers
By gapper in forum New To JavaReplies: 3Last Post: 02072008, 10:09 AM
Bookmarks