Problem 010

[kapman]

For your info, my algo runs in 12 ms on a 2-year-old CoreDuo 1.9GHz for the 2000000 limit. My timing is 6 ms for the 1000000 limit (on the same computer).

Tanks for the result. At least I'm quite happy with my Algo running in 6.7ms and 3ms on a little newer machine with 3GHz.

Still, I wonder what happened to the solution thread?

[Inglonias]

As I speak, I'm running a java program that's brute-forcing the solution. There's a better way, isn't there? I'm currently in the 550,000 area. *Sigh*

[hk]

Yes there is.
And I advise you to break off your bruteforcing program and start thinking about better solutions.

[Inglonias]

Done. I fixed the program. Brute forcing isn't so bad if you start with the square root of the number when checking for factors. Ok, its not great (6.72 seconds) but its a start.

EDIT: After reading the overview, I see the sieve now. I was marginally aware of it by browsing this topic beforehand, but I don't quite understand how it works. I'll ask one of my teachers.

EDIT 2: Got the brute forcer down to 4.4 seconds.

[Coda17]

The Wikipedia article for that sieve you speak of is very good for people who have never seen it before. It's very useful for lots of the problems here at PE.

[Inglonias]

Ha HA!

Code: Select all

Brute force from 1 to square root of 2000000
Sum: *I'm not telling*
DONE! It took 20.424194415 seconds to run this code.

Sieve of Eratosthenes:
Sum: *I'm still not telling*
DONE! It took 0.084647909 seconds to run this code.

This is on a school-owned Latitude D610 Laptop (It sucks). I'm running Eclipse off my memory key. This is a HUGE difference in time taken. Woot!

Thanks for all your help, guys.

[hk]

You're welcome.
It's quite a good rule to break off bruteforcing solutions if they tend to take too long and start thinking about better solutions. Some research on Wikipedia might be quite helpful.

[phix]

Hey ! I have implemented the Sieve of Eratosthenes logarithm but the actual creation of the list takes ages for me since I kind of bruteforced the non brute force way lol. I am currently learning to program by myself and with books I have bought (python by the way) and so far the first few problems wern't too much of a hassle but this one how can I create the list faster so I can implement this logarithm ?

Wish I could post my code but that would be against rules, I know I'm missing just a little tiny step, probably because of my lack of knowledge

[elendiastarman]

Hey ! I have implemented the Sieve of Eratosthenes logarithm but the actual creation of the list takes ages for me since I kind of bruteforced the non brute force way lol. I am currently learning to program by myself and with books I have bought (python by the way) and so far the first few problems wern't too much of a hassle but this one how can I create the list faster so I can implement this logarithm ?

Wish I could post my code but that would be against rules, I know I'm missing just a little tiny step, probably because of my lack of knowledge

Are you producing the primes and THEN sieving? If so, why don't you try building the prime list alongside of the sieve? Like...every time your sieve finds a prime, it adds that prime to the list and keeps sieving.

[phix]

Hey ! I have implemented the Sieve of Eratosthenes logarithm but the actual creation of the list takes ages for me since I kind of bruteforced the non brute force way lol. I am currently learning to program by myself and with books I have bought (python by the way) and so far the first few problems wern't too much of a hassle but this one how can I create the list faster so I can implement this logarithm ?

Wish I could post my code but that would be against rules, I know I'm missing just a little tiny step, probably because of my lack of knowledge

Are you producing the primes and THEN sieving? If so, why don't you try building the prime list alongside of the sieve? Like...every time your sieve finds a prime, it adds that prime to the list and keeps sieving.

LOOOOOOOOOOL I know what I was doing wrong omg... you guys are probably going to laugh your asses off.

I was trying to find the sum of the first 2 million primes, instead of the sum of the primes below the number 2000000 LOOOOL thats why my answer was always wrong...

I don't know if i have explained myself I was adding each prime 2,3,5,7, etc and each prime found counted as 1, so the sum of the first 4 primes is 17, while the problem was asking the sum of the primes below the number 4, aka > 2,3 so >>5.

*Slaps self across the face and picks up all the hair from the floor that fell due to stress trying to make this problem work XDDD*


Btw when I did the problem the wrong way (obviously it takes way longer) I did it both with C and Python and I was amazed at how much faster C was, I mean I knew it was faster, but not lightening years fast...

[cdd]

I can get my program to work for the sums below 10 000 but anything about takes too long. Any tips for dealing with really big numbers too? Im using the Sieve of Eros... to find the primes.

[GenePeer]

You may have an overflow in the final answer if you're using 32-bit integers, e.g.,int in Java.

Are you sure you implemented the sieve properly?

[cdd]

My values to sums below 10000 are correct. My program works by creating a vector whos digits are all of the odd numbers up to a certain digit. then i let the sieve go through the list of number erasing the digits acordingly. After the sieve is done i sum the vector elements left, where my sum variable is a long double. I think my problem is that i a vector 1 000 000 digits long is too much memory. Im using c++, any suggestions?

[GenePeer]

Try using a boolean array instead.

[cdd]

how would a Boolean Array be useful if when you want to create a list of numbers?

[GenePeer]

array[n] is true for prime number n.

[cdd]

hey,
so i reprogrammed the program to use a boolean vector and the results do come much faster, however some are incorrect. Ive checked with values on the internet and my program gets the sum of primes under 10 and 100 correct, but when i test it at 1000 the value is in correct. Could i pm my code to someone for them to check??

[GenePeer]

hey,
so i reprogrammed the program to use a boolean vector and the results do come much faster, however some are incorrect. Ive checked with values on the internet and my program gets the sum of primes under 10 and 100 correct, but when i test it at 1000 the value is in correct. Could i pm my code to someone for them to check??

Since I only know Java (which is similar to c++), I don't know how vectors work well enough to debug. So if you can rewrite it with a boolean array, I could check.

[thundre]

hey,
so i reprogrammed the program to use a boolean vector and the results do come much faster, however some are incorrect. Ive checked with values on the internet and my program gets the sum of primes under 10 and 100 correct, but when i test it at 1000 the value is in correct. Could i pm my code to someone for them to check??

I'm not sure what language you're using. If it's Java, the performance of Vector is great if you're reading it or if you're adding/deleting near the end. But I think it stores the terms as an array, so if you add/delete near the beginning performance is very bad, and it changes the indices for everything after it. The suggestion of an array was a good one. Modern computers usually have at least 1000 MB (1 GB) of memory, so an array of 2M int/long/boolean is not a problem.

A hint about the sieve: If n is the product of more than one prime, what can you say about the lowest of those primes?

[cdd]

im using c++, the problem im having isnt so much with run time. for 2 million it runs in about 30 seconds to a minute, which i know isnt the best. The problem is that the program only works for the sum of primes under 100 but when i try under 1000 and bigger the number it gives is incorrect.