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:

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 = " + (endTime-startTime) + " milliseconds");

} //end of main

}

Thanks!

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,

Jos

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!

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

Re: My program has to run in less than a minute. Can anyone help make my code efficie

Quote:

Originally Posted by

**AndrewM16921** 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

It did speed up by about half. Wow, thank you! What's so bad about math.sqrt()?

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?

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.

Re: My program has to run in less than a minute. Can anyone help make my code efficie

Quote:

Originally Posted by

**AndrewM16921** 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.

Awesome explanation there :)

Also, math.sqrt() takes longer because it's a method right or I'll just go with your explanation?

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)

Code:

`JNIEXPORT jdouble JNICALL`

Java_java_lang_StrictMath_sqrt(JNIEnv *env, jclass unused, jdouble d)

{

return (jdouble) jsqrt((double)d);

}

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

}

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((ix0|ix1)!=0) {

z = one-tiny; /* 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;

}

And nope, I have no idea what's going on there ^

Re: My program has to run in less than a minute. Can anyone help make my code efficie

Quote:

Originally Posted by

**jamgor** ^ I'm not allowed to use that algorithm haha!

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*n-1 or 6*n+1 (except 2 and 3); you can use that fact in your loop for an additional speed up.

Jos

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,

Jim

Re: My program has to run in less than a minute. Can anyone help make my code efficie

Quote:

Originally Posted by

**jim829** 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.

That's a sieve and the OP is not allowed to use it (for reasons that are beyond me).

kind regards,

Jos

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,

Jim

Re: My program has to run in less than a minute. Can anyone help make my code efficie

Quote:

Originally Posted by

**jim829** 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?

Think of the 'classic' sieve: you take the next number that is definitely prime and mark out all multiples thereof; you start with number 2 (definitely a prime). Compare this with what you suggested ...

kind regards,

Jos

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 sub-optimal 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,

Jim