Results 1 to 4 of 4
  1. #1
    hvince95 is offline Member
    Join Date
    Jan 2012
    Location
    Adelaide, Australia
    Posts
    17
    Rep Power
    0

    Default Optimising this simple piece of code (30 lines)

    For Project Euler :)
    This fairly simple piece of code works great, around 600ms to calculate the sum of all primes below 2 million:

    Java Code:
    public class projectEuler {
    	
    	public static void main (String [] args) {
    		
    		double startTime = System.nanoTime();
    		
    		int testNum = 1;
    		long count = 0;
    		while(testNum < 2000000){
    			testNum++;
    			if(primeTest(testNum)){
    				count += testNum;
    			}
    		}
    		System.out.println(count);
    		System.out.println(((double)System.nanoTime() - startTime) / 1000000000);
    		
    	}
    	
    	public static boolean primeTest(int n) {
    
    		if (n == 2 || n == 3)
    			return true;
    		if (n < 2 || n % 2 == 0)
    			return false;
    
    		int sn = (int) Math.round(Math.sqrt(n) + 1);
    		for (int a = 3; a <= sn; a += 2)
    			if (n % a == 0)
    				return false;
    
    		return true;
    	}
    }
    Others have been getting really, really fast times (easily under 100ms). Could someone please help optimise this code with me?
    Thanks.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,708
    Rep Power
    13

    Default Re: Optimising this simple piece of code (30 lines)

    Java Code:
    if (n == 2 || n == 3)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
    This code can be removed - just don't call the method with small or even n. (In those cases you know what is going to be returned.)

    -----

    Java Code:
    for (int a = 3; a <= sn; a += 2)
    This code checks all of the odd numbers from 3 for a factor. Those numbers are:

    3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...

    This is a bit wasteful since 1/3 of the trial factors are themselves multiples of 3 and you have already ruled out 3 as a factor. Think about how you might check 5 and 7 and then jump to 11, check 11 and 13 and then jump to 17, etc.

  3. #3
    hvince95 is offline Member
    Join Date
    Jan 2012
    Location
    Adelaide, Australia
    Posts
    17
    Rep Power
    0

    Default Re: Optimising this simple piece of code (30 lines)

    ok, cheers mate.

    I'll have to implement some of that.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,051
    Blog Entries
    7
    Rep Power
    23

    Default Re: Optimising this simple piece of code (30 lines)

    Quote Originally Posted by pbrockway2 View Post
    This code can be removed - just don't call the method with small or even n. (In those cases you know what is going to be returned.)
    That code is a nice atttempt to protect the real body of the method against trivial cases; a better attempt is:

    Java Code:
    if (n < 2) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    The next part of the code only has to check if n is of the form 6*p+-1 (the other values are most certainly not prime).

    kind regards,

    Jos
    Last edited by JosAH; 01-29-2012 at 09:47 AM.
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Giant Piece of Code and want it somewhere else.
    By thatguywhoprograms in forum New To Java
    Replies: 1
    Last Post: 12-19-2011, 07:26 PM
  2. Need help with a piece of code
    By sneeak in forum New To Java
    Replies: 13
    Last Post: 08-24-2011, 10:51 AM
  3. Code to check if a piece of code is legal.
    By vahshir in forum New To Java
    Replies: 3
    Last Post: 08-30-2010, 04:21 AM
  4. small piece of code: cannot set a max
    By senca in forum New To Java
    Replies: 1
    Last Post: 03-06-2010, 09:26 PM
  5. Decode this piece of Code
    By mikeyl62 in forum New To Java
    Replies: 2
    Last Post: 02-27-2010, 09:59 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
  •