Velocity Reviews > Java > [Algorithm] Sum of Primes < 1000000

# [Algorithm] Sum of Primes < 1000000

Luc The Perverse
Guest
Posts: n/a

 01-05-2007
I was messing around on a site where you answer questions for points. (No
prizes or anything)

Anyway, they say our programs *should* execute in less than 1 minute if well
formed.

Mine didn't - it was less than 10 minutes though and I got the right answer.

I was supposed to sum all primes less than 1 million.

Is there an algorithm out there, which I will be able to understand, which
works significantly faster than this one?

//import java.lang.*;
import java.util.*;
import java.math.*;

public class prob10{
public static void main(String[] x){
if(x.length<1){
System.out.println("enter a number");
return;
}

int n = Integer.parseInt(x[0]);
int c = 0;
int[] pc = new int[n];
int[] p2 = new int[n];
if(n<=1){
System.out.println(2);
return;
}
c++;
pc[0] = 2;
p2[0] = 2;
int cn = 1;
long g = 2;
while(c<n){
cn+=2;
boolean Prime = true;
for(int i=1;i<c;i++){
p2[i] -= 2;
if(p2[i] == 0)
Prime = false;
if(p2[i] < 1)
p2[i] += pc[i];
}
if(Prime){
pc[c] = cn;
p2[c++] = cn;
if((c%204 == 0)
System.out.println(cn);
if(cn<1000000)
g+=cn;
else{
System.out.println("Yay 1 million reached!");
break;
}

}
}
System.out.println("Grand Total " + g);
System.out.println(pc[n-1]);
}

}

I specifically tried to avoid ever dividing or modding (except in my status
reporter, but that only checks when a prime has been found)

I "count down" until the next multiple a prime is detected.

The algorithm works . . but it is n^2 complexity, and kinda sucks.

--
LTP

Simon
Guest
Posts: n/a

 01-05-2007
Luc The Perverse schrieb:
> I was messing around on a site where you answer questions for points. (No
> prizes or anything)
>
> Anyway, they say our programs *should* execute in less than 1 minute if well
> formed.
>
> Mine didn't - it was less than 10 minutes though and I got the right answer.
>
> I was supposed to sum all primes less than 1 million.
>
> Is there an algorithm out there, which I will be able to understand, which
> works significantly faster than this one?

You may want to have a look at the Sieve of Eratosthenes (and its successors)
(see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It finds all primes up
to n in time n log n. On my computer my implementation takes 150 milliseconds
for n=1000000.

> I specifically tried to avoid ever dividing or modding (except in my status
> reporter, but that only checks when a prime has been found)

I doubt that such micro-optimisations are of much use here.

Cheers,
Simon

Patricia Shanahan
Guest
Posts: n/a

 01-05-2007
Luc The Perverse wrote:
> I was messing around on a site where you answer questions for points. (No
> prizes or anything)
>
> Anyway, they say our programs *should* execute in less than 1 minute if well
> formed.
>
> Mine didn't - it was less than 10 minutes though and I got the right answer.
>
> I was supposed to sum all primes less than 1 million.
>
> Is there an algorithm out there, which I will be able to understand, which
> works significantly faster than this one?

....

The usual algorithm is the Sieve of Eratosthenes,
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The sieve is O(n*n), but with small constant factor.

Patricia

Patricia Shanahan
Guest
Posts: n/a

 01-05-2007
Patricia Shanahan wrote:
> Luc The Perverse wrote:
>> I was messing around on a site where you answer questions for points.
>> (No prizes or anything)
>>
>> Anyway, they say our programs *should* execute in less than 1 minute
>> if well formed.
>>
>> Mine didn't - it was less than 10 minutes though and I got the right
>>
>> I was supposed to sum all primes less than 1 million.
>>
>> Is there an algorithm out there, which I will be able to understand,
>> which works significantly faster than this one?

> ...
>
> The usual algorithm is the Sieve of Eratosthenes,
> http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
>
> The sieve is O(n*n), but with small constant factor.

I was wrong about the complexity. I was not allowing for only doing the
inner loop for primes.

Patricia

Luc The Perverse
Guest
Posts: n/a

 01-05-2007
"Patricia Shanahan" <(E-Mail Removed)> wrote in message
news:Cernh.6752\$(E-Mail Removed) ink.net...
> Patricia Shanahan wrote:
>> Luc The Perverse wrote:
>>> I was messing around on a site where you answer questions for points.
>>> (No prizes or anything)
>>>
>>> Anyway, they say our programs *should* execute in less than 1 minute if
>>> well formed.
>>>
>>> Mine didn't - it was less than 10 minutes though and I got the right
>>>
>>> I was supposed to sum all primes less than 1 million.
>>>
>>> Is there an algorithm out there, which I will be able to understand,
>>> which works significantly faster than this one?

>> ...
>>
>> The usual algorithm is the Sieve of Eratosthenes,
>> http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
>>
>> The sieve is O(n*n), but with small constant factor.

>
> I was wrong about the complexity. I was not allowing for only doing the
> inner loop for primes.

Looks like I had better check this out!

hehe cool

Thanks guys! (And I mean Simon too)

--
LTP

Patricia Shanahan
Guest
Posts: n/a

 01-05-2007
Simon wrote:
> Luc The Perverse schrieb:
>> I was messing around on a site where you answer questions for points. (No
>> prizes or anything)
>>
>> Anyway, they say our programs *should* execute in less than 1 minute if well
>> formed.
>>
>> Mine didn't - it was less than 10 minutes though and I got the right answer.
>>
>> I was supposed to sum all primes less than 1 million.
>>
>> Is there an algorithm out there, which I will be able to understand, which
>> works significantly faster than this one?

>
> You may want to have a look at the Sieve of Eratosthenes (and its successors)
> (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It finds all primes up
> to n in time n log n. On my computer my implementation takes 150 milliseconds
> for n=1000000.

As a matter of curiosity, did you use a boolean[] or BitSet?

I started with a boolean[], and mine was slower than yours, about 200
milliseconds. It dropped to under 100 milliseconds when I switched to
BitSet. I believe the improvement is due to more efficient caching.

Patricia

Daniel Pitts
Guest
Posts: n/a

 01-05-2007

Patricia Shanahan wrote:
> Simon wrote:
> > Luc The Perverse schrieb:
> >> I was messing around on a site where you answer questions for points. (No
> >> prizes or anything)
> >>
> >> Anyway, they say our programs *should* execute in less than 1 minute if well
> >> formed.
> >>
> >> Mine didn't - it was less than 10 minutes though and I got the right answer.
> >>
> >> I was supposed to sum all primes less than 1 million.
> >>
> >> Is there an algorithm out there, which I will be able to understand, which
> >> works significantly faster than this one?

> >
> > You may want to have a look at the Sieve of Eratosthenes (and its successors)
> > (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It finds all primes up
> > to n in time n log n. On my computer my implementation takes 150 milliseconds
> > for n=1000000.

>
> As a matter of curiosity, did you use a boolean[] or BitSet?
>
> I started with a boolean[], and mine was slower than yours, about 200
> milliseconds. It dropped to under 100 milliseconds when I switched to
> BitSet. I believe the improvement is due to more efficient caching.
>
> Patricia

I personally got 66ms from:

public class SumPrimes {
public static void main(String...args) {
final int bounds = Integer.parseInt(args[0]) + 1;
final java.util.BitSet composits = new
java.util.BitSet(bounds);
long sum = 1;
for (int prime = 2; prime < bounds; prime =
composits.nextClearBit(prime +1)) {
sum += prime;
for (int composit = prime + prime; composit < bounds;
composit += prime) {
composits.set(composit);
}
}
System.out.println(sum);
}
}

MikeNereson
Guest
Posts: n/a

 01-06-2007
Your original alogorithm worked for me in 141ms. I made a couple
seemingly minor changes. Can you find them? Why are they so important?

http://pastebin.com/852736

OUTPUT:
Yay 1 million reached!
Grand Total 797162
0
only took 141 ms

MikeNereson
Guest
Posts: n/a

 01-06-2007
Whoops, I didn't validate that output. My bad. The bitset solution is
great.

MikeNereson wrote:
> Your original alogorithm worked for me in 141ms. I made a couple
> seemingly minor changes. Can you find them? Why are they so important?
>
> http://pastebin.com/852736
>
> OUTPUT:
> Yay 1 million reached!
> Grand Total 797162
> 0
> only took 141 ms

Chris Uppal
Guest
Posts: n/a

 01-06-2007
MikeNereson wrote:

> Yay 1 million reached!
> Grand Total 797162

Seems unlikely to be the correct answer since 999983 is just one one of the
primes in that range...

-- chris