Results 1 to 6 of 6
  1. #1
    Zigster is offline Member
    Join Date
    Apr 2012
    Posts
    74
    Rep Power
    0

    Default Speed up program?

    I created a program to give me the sum of all prime numbers below 2 million. It works, but it takes a really long time to process. I have tried to fiddle around with it, trying to figure out where I can take out ifs and such, but hasn't made any difference. How can I make it go faster?

    Java Code:
    public class Problem10 {
    	public static void main (String[] args){
    		
    		int x, y;
    		long a = 0;
    		
    		for (x= 2; x <= 2000000; x++)
    		{
    			if (x==2000000)
    			{
    			System.out.println("The sum of all the primes below two million:" + a);
    			System.exit(0);
    			}
    			
    			y=2;
    			outerloop:
    				do 
    				{
    					
    					if (PrimeN(x, y))
    					{
    					break outerloop;
    					}
    					y++;
    					}
    					while (y<x);
    			
    				if (x==y)
    				{
    				a +=x;
    				
    				}
    					
    				
    		}
    	}	
    	
    	
    	public static boolean PrimeN(int a, int b){
    
    		if (a%b==0){
    			return true;
    		}
    
    		else
    		{
    			return false;
    		}
    		
    	}
    
    }
    Cheers!

  2. #2
    DarrylBurke's Avatar
    DarrylBurke is online now Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,407
    Rep Power
    20

    Default Re: Speed up program?

    For one, you could cut down on the iterations by using while(y * y < x). think about why that's valid first.

    There are probably other optimizations possible.

    db
    Last edited by DarrylBurke; 04-25-2012 at 12:51 PM.
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,559
    Rep Power
    25

    Default Re: Speed up program?

    Remove the PrimeN method. It only does one thing that could be done in-line.
    If you don't understand my response, don't ignore it, ask a question.

  4. #4
    Zigster is offline Member
    Join Date
    Apr 2012
    Posts
    74
    Rep Power
    0

    Default Re: Speed up program?

    Yes, because if y * y = x, x is not a prime number. Thanks, I will try it and see if it speeds up. Ok thanks I will remove the PrimeN method too.

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

    Default Re: Speed up program?

    Use a Sieve for finding those prime numbers; a couple of million bits isn't that much and the creation of a Sieve is fast.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Zigster is offline Member
    Join Date
    Apr 2012
    Posts
    74
    Rep Power
    0

    Default Re: Speed up program?

    Quote Originally Posted by JosAH View Post
    Use a Sieve for finding those prime numbers; a couple of million bits isn't that much and the creation of a Sieve is fast.

    kind regards,

    Jos
    Thanks Jos, that looks awesome!

Similar Threads

  1. Need help to speed up algorithm
    By XAW in forum New To Java
    Replies: 5
    Last Post: 04-07-2012, 02:01 AM
  2. Set max upload speed
    By Giuseppe_Mazzei in forum New To Java
    Replies: 9
    Last Post: 06-03-2011, 02:28 AM
  3. Replies: 0
    Last Post: 03-18-2011, 08:48 PM
  4. How to speed sql Statements?
    By bezudar in forum Advanced Java
    Replies: 3
    Last Post: 11-20-2008, 09:53 AM
  5. compare speed
    By bbq in forum JDBC
    Replies: 1
    Last Post: 06-28-2007, 05:34 PM

Posting Permissions

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