Results 1 to 6 of 6
  1. #1
    Draco is offline Member
    Join Date
    Jun 2012
    Posts
    1
    Rep Power
    0

    Default 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. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

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

    Default 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. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Singing Boyo is offline Senior Member
    Join Date
    Mar 2009
    Posts
    552
    Rep Power
    6

    Default Re: More Efficient Prime Searching Algorithm?

    Quote Originally Posted by JosAH View Post
    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;
    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!

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default Re: More Efficient Prime Searching Algorithm?

    Quote Originally Posted by Singing Boyo View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Big prime
    By diamonddragon in forum New To Java
    Replies: 25
    Last Post: 02-02-2012, 11:04 PM
  2. Palindromic Prime?
    By soccergirl67 in forum New To Java
    Replies: 5
    Last Post: 12-01-2011, 09:48 AM
  3. Prime Number - System print all the prime numbers ...
    By pinkdreammsss in forum New To Java
    Replies: 20
    Last Post: 04-26-2009, 01:50 AM
  4. Prime numbers
    By tercius in forum New To Java
    Replies: 3
    Last Post: 05-04-2008, 06:05 AM
  5. Prime numbers
    By gapper in forum New To Java
    Replies: 3
    Last Post: 02-07-2008, 10:09 AM

Posting Permissions

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