Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

[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




 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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
>> 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.


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

Patricia
 
Reply With Quote
 
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
>>> 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.

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




 
Reply With Quote
 
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
 
Reply With Quote
 
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);
}
}

 
Reply With Quote
 
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

 
Reply With Quote
 
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


 
Reply With Quote
 
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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Return value of 1000000 from recv.. why? Tim Shephard C Programming 3 08-30-2010 02:13 PM
Re: 1.090516455488E9 / 1000000.000 ??? Math Python 2 03-29-2006 10:49 AM
1.090516455488E9 / 1000000.000 ??? Math Python 2 03-28-2006 03:30 PM
regex to convert 1000000 -> 1,000,000 ? bad_knee Perl Misc 39 11-19-2003 02:11 PM
Crypt RSA install (Problem with Crypt::Primes) AdrianK Perl 0 07-09-2003 09:32 AM



Advertisments