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,565
    Rep Power
    12

    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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    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 08:47 AM.
    cenosillicaphobia: the fear for an empty beer glass

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, 06: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, 08:26 PM
  5. Decode this piece of Code
    By mikeyl62 in forum New To Java
    Replies: 2
    Last Post: 02-27-2010, 08: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
  •