Results 1 to 15 of 15
 06122013, 04:04 AM #1Member
 Join Date
 Jun 2013
 Posts
 12
 Rep Power
 0
My program has to run in less than a minute. Can anyone help make my code efficient?
Hey all. I am trying to find the millionth prime number. My code's functionality is fine, but it takes too long to run (about 3 minutes)
I want to make it run in about a minute or less. Here's my code:
Java Code:import java.util.*; public class Mainn { public static void main(String[] args) { int count = 0; int number = 2; ArrayList <Integer> a = new ArrayList(); while(count < 1000000) { int c=0; for(int i = 2; i <= Math.sqrt(number) ; i++) { if (number%i == 0) //check to see if it is even { c=1; break; //end loop if even } } if(c==0) { a.add(number); count++; } number++; }//end of while System.out.println(a.get(a.size()1)); //prints last element of the arraylist which is the 1 millionth prime number long startTime = System.currentTimeMillis(); long total = 0; for (int i = 0; i < 1000000; i++) { total += i; } long endTime = System.currentTimeMillis(); System.out.println("Runtime = " + (endTimestartTime) + " milliseconds"); } //end of main }
 06122013, 09:05 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Use a 'Sieve of Eratosthenes' and a BitSet; Google is your friend here.
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 06132013, 01:14 AM #3Member
 Join Date
 Jun 2013
 Posts
 12
 Rep Power
 0
Re: My program has to run in less than a minute. Can anyone help make my code efficie
^ I'm not allowed to use that algorithm haha!
 06132013, 01:23 AM #4Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 271
 Rep Power
 8
Re: My program has to run in less than a minute. Can anyone help make my code efficie
One small note.
Math.sqrt() is relatively expensive, try comparing i*i <= number, instead.
This is the change for me running your program (moved startTime to top of main, also) before and after that change (on average, it takes half the time):
BEFORE: Runtime = 22081 milliseconds
AFTER: Runtime = 10915 milliseconds
 06132013, 02:29 AM #5Member
 Join Date
 Jun 2013
 Posts
 12
 Rep Power
 0
 06132013, 02:32 AM #6Member
 Join Date
 Jun 2013
 Posts
 12
 Rep Power
 0
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Having just learned what a hashmap is, would it be more efficient than an arraylist here?
 06132013, 03:01 AM #7Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 271
 Rep Power
 8
Re: My program has to run in less than a minute. Can anyone help make my code efficie
HashMap is good if you're searching for items in a collection (or HashSet, in this case). But if you're just iterating through the list linearly, an ArrayList is ideal.
Also, keep in my that when it comes to these data structures (Sets, and HashMap) the ordering of the data is not necessarily preserved and duplicates are overwritten.
Not sure exactly, but I know the algorithms for calculating a square root are WAY more intense than those for simply multiplying 2 numbers. :P
If you ever see a lot of physics engines or games, they often used the squared value rather than the actual value for distance comparisons. This is why vector type classes have a distance() method as well as a distanceSquared() method  for performance.Last edited by AndrewM16921; 06132013 at 03:06 AM.
 06132013, 03:18 AM #8Member
 Join Date
 Jun 2013
 Posts
 12
 Rep Power
 0
 06132013, 03:43 AM #9Senior Member
 Join Date
 Jan 2009
 Location
 CA, USA
 Posts
 271
 Rep Power
 8
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Lol, not exactly. Let me put it this way. In OpenJDK, sqrt is defined like this:
(note it's native code, not java code)
Java Code:JNIEXPORT jdouble JNICALL Java_java_lang_StrictMath_sqrt(JNIEnv *env, jclass unused, jdouble d) { return (jdouble) jsqrt((double)d); }
Java Code:#ifdef __STDC__ double sqrt(double x) /* wrapper sqrt */ #else double sqrt(x) /* wrapper sqrt */ double x; #endif { #ifdef _IEEE_LIBM return __ieee754_sqrt(x); #else double z; z = __ieee754_sqrt(x); if(_LIB_VERSION == _IEEE_  isnan(x)) return z; if(x<0.0) { return __kernel_standard(x,x,26); /* sqrt(negative) */ } else return z; #endif }
Java Code:/* generate sqrt(x) bit by bit */ ix0 += ix0 + ((ix1&sign)>>31); ix1 += ix1; q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */ r = 0x00200000; /* r = moving bit from right to left */ while(r!=0) { t = s0+r; if(t<=ix0) { s0 = t+r; ix0 = t; q += r; } ix0 += ix0 + ((ix1&sign)>>31); ix1 += ix1; r>>=1; } r = sign; while(r!=0) { t1 = s1+r; t = s0; if((t<ix0)((t==ix0)&&(t1<=ix1))) { s1 = t1+r; if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1; ix0 = t; if (ix1 < t1) ix0 = 1; ix1 = t1; q1 += r; } ix0 += ix0 + ((ix1&sign)>>31); ix1 += ix1; r>>=1; } /* use floating add to find out rounding direction */ if((ix0ix1)!=0) { z = onetiny; /* trigger inexact flag */ if (z>=one) { z = one+tiny; if (q1==(unsigned)0xffffffff) { q1=0; q += 1;} else if (z>one) { if (q1==(unsigned)0xfffffffe) q+=1; q1+=2; } else q1 += (q1&1); } } ix0 = (q>>1)+0x3fe00000; ix1 = q1>>1; if ((q&1)==1) ix1 = sign; ix0 += (m <<20); __HI(z) = ix0; __LO(z) = ix1; return z; }
 06132013, 09:55 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Very funny indeed; you want one of the fastest algorithms but you're now allowed (by who?) to use a very efficient algorithm; beside that fiddiling with the Math.sqrt(x) method, note that all primes are of the form 6*n1 or 6*n+1 (except 2 and 3); you can use that fact in your loop for an additional speed up.
JosThe only person who got everything done by Friday was Robinson Crusoe.
 06132013, 05:14 PM #11Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 5,738
 Rep Power
 10
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Also, don't divide by every integer up to the square root of the number. Only divide by the primes you have already computed < square root of the number. And don't use System.currentTimeMillis() to time your result. Use System.nanoTime().
Regards,
JimLast edited by jim829; 06132013 at 05:20 PM.
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06132013, 05:35 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
 06132013, 05:49 PM #13Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 5,738
 Rep Power
 10
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Hmm, I implemented Eratosthenes' sieve many years ago but I didn't equate that to what I just recommended. I was just applying the fundamental theorem of arithmetic. I wonder if the OP is allowed to only check odd numbers > 2?
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 06132013, 06:01 PM #14
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
Re: My program has to run in less than a minute. Can anyone help make my code efficie
The only person who got everything done by Friday was Robinson Crusoe.
 06132013, 06:19 PM #15Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 5,738
 Rep Power
 10
Re: My program has to run in less than a minute. Can anyone help make my code efficie
Well, I found this on Wiki and started to read some of the footnote references:
"Trial division can be used to produce primes by filtering out the composites found by testing each candidate number for divisibility by its preceding primes. It is often confused with the sieve of Eratosthenes, although the latter directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.^{[2]}
When testing each candidate number, the optimal trial division algorithm uses just those prime numbers not exceeding its square root. The widely known 1975 functional code by David Turner^{[9]} is often presented as an example of the sieve of Eratosthenes^{[8]} but is actually a suboptimal trial division algorithm.^{[2]}"
I read parts of the paper cited in the article in [2] above. It discusses a way of actually using the sieve to compute primes with an infinite upper bound. I may have to try it out.
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
Similar Threads

Anyway I could "clean up" or make this simple program more efficient/better?
By psx2514 in forum New To JavaReplies: 5Last Post: 03142013, 12:39 PM 
The Most Efficient Way To Make a 2D Game?
By TacoManStan in forum New To JavaReplies: 5Last Post: 01262012, 09:57 PM 
How to make my program more efficient?
By LonelyClock in forum New To JavaReplies: 9Last Post: 11292011, 05:47 AM 
more efficient way to make this??? [LOOK]
By Green in forum New To JavaReplies: 10Last Post: 09092011, 01:01 AM 
Need some help with code. Make it more efficient.
By Meta in forum New To JavaReplies: 1Last Post: 03222010, 09:21 AM
Bookmarks