Problem 010

[cdd]

thanks for the help, i figured it out though, had a useless iterator screwing up my sum.

[ishkabible]

ok so i can't figure out whats wrong with my code. i am constructing a vector<bool>(im using C++) using the Sieve Of Eratosthenes such that the indexes of prime numbers are true and the indexes of composite numbers are false. then i loop though the array checking to see if the index is prime, if it is then i add that index to the sum. for some reason i keep getting the same answer. i am using unsigned long long for all my integer values(even though only the sum should need it). im just plain stumped on this one.

edit: oops, sometimes writing it out helps, i did everything right expect the return value on my function as 'int'

[jcampos8782]

I am having a problem with a segmentation fault when attempting to solve problem #10 (sum of primes under 2,000,000). I am trying to solve using C, on Windows 7, in Cywin, and compiling with the most recent version of GCC.

Now I will try to explain without giving away details... I am trying to make a really big array and solve using a well known method for finding primes... I Googled this problem and it does not appear that people are having an issue with segmentation when creating such a large array, but for some reason I am. Is this a known issue in Cygwin or Windows 7? Is there a compiler option I can use to allow for larger arrays in memory? Not exactly sure how to work around this problem without resorting to solving in another language but I prefer to solve these problems in C.

If you want more details, I can post them.

UPDATE: PROBLEM SOLVED (SEGMENTATION PROBLEM THAT IS)... if you run into the same problem, feel free to PM me for help on that.

[anubhav_pro]

here is the code i have written in java- it game me answer in 1 sec :

[frogjg2003]

I have a solution but it's taking forever.
I'm using Euler's sieve and i've been running it for about 10 hours (if you don't count the time my computer went into hybernate) and it's only on 17.
I can provide the code to anyone willing to look at it.

[Francky]

In python such a method is about half a second to take.
10h means your implementation is incorrect.
You should read again your code and this method.
You can pm me your code, I'll try to see.

[cruxae]

Haha...I thought I was doing this wrong, when I realised I should try making my "int sum=0" into "long sum=0"
And it worked
I think the answer was overflowing....

[kjp1212]

Okay here is the issue, I don't have a freakin clue as to how to implement Sieve of Eratosthenes. I read it in wiki, but I'm not sure how to implement it. I mean I looked through earlier posts but still cant figure it out. I came across the sieve in an earlier problem but I used something else that we all used in primary school(it should be obvious to those who solved it) and did not use the sieve.

This 10th problem, I cant find any other way, plus I hear this "Sieve" is a really useful method for later problems too. So can someone help me out here.

BTW, I am currently trying to do the problem with brute force plus the extra addons we get from the pdf file unlocked after solving problem no:7. I also tried another way in which I create a list of primes and keep on adding to this list as we go through the range (from 7 to 2,000,000 and of course while checking a new number I used only the numbers within this list).It takes far more than 1 minute. I am using python

[hk]

On the wikipedia page there is an implementation in pseudo code: http://en.wikipedia.org/wiki/Sieve_of_E ... ementation
This should tell you how to implement it.
Did you study that pseudocode?
If so, what is the problem with that pseudocode?

[kjp1212]

On the wikipedia page there is an implementation in pseudo code: http://en.wikipedia.org/wiki/Sieve_of_E ... ementation
This should tell you how to implement it.
Did you study that pseudocode?
If so, what is the problem with that pseudocode?

Yeah.....the thing is wont we have to make a list of 2 million numbers to apply that pseudocode ?????? I mean isn't there some other efficient way

[Lord_Farin]

Yeah.....the thing is wont we have to make a list of 2 million numbers to apply that pseudocode ?????? I mean isn't there some other efficient way

In the end, there isn't really. One could use the fact that 2 is the only even prime to bring it down to 1 million. Then, as the primeQ flag is just a bit, you only need about 128kB of memory, which I'm sure your computer has

[martix]

Primes are a b*tch to deal with on a case-by-case basis.
They are also common as dirt around this site.

So users have 2 options.
Either sit down and write a proper library, class, whatever to which they can refer when needed.
OR
Use software/code which already has those features(custom libraries, Matlab, Mathematica or its online version http://www.wolframalpha.com).

[hk]

On the wikipedia page there is an implementation in pseudo code: http://en.wikipedia.org/wiki/Sieve_of_E ... ementation
This should tell you how to implement it.
Did you study that pseudocode?
If so, what is the problem with that pseudocode?

Yeah.....the thing is wont we have to make a list of 2 million numbers to apply that pseudocode ?????? I mean isn't there some other efficient way

The pseudocode states that you should make an array of boolean values, not an array of numbers.
Lookup in the documentation of your programming language how boolean values are handled.

[kjp1212]

Thanks to hk, matrix, Lord Farin for all your help . Man I'm starting to get addicted to this site

[Infamous911]

So I'm pretty sure I've successfully coded the solution to the problem (in Java), but the program takes a very long time to finish. So long in fact, that I haven't sat through its completion yet. The code simply goes through every number less than two million and checks to see if it's divisible by every single number up to itself.

Any ideas on how to make this finish faster?

[hk]

Did you read the pdf for problem 007? (I can see you solved that one).

(By the way you're not supposed to post code fragments for PE problems in this forum. Could you remove your code, please?)

[dmch2]

My first attempt was a brute force one but rather that checking whether every number is a factor you only need to go up to the rootn(rounded up) of it. So when looking for factors of 101 you only need to check up to 11. This only took 9 seconds for me.

It was still my slowest solution yet so I tried using a sieve but it only reduced the time to 1 second. So worth the (slight) effort but not as dramatically faster as I expected.

[thundre]

It was still my slowest solution yet so I tried using a sieve but it only reduced the time to 1 second. So worth the (slight) effort but not as dramatically faster as I expected.

There are many, many more problems in which a prime sieve is useful. You will be glad you coded it.

[avantika]

hello everyone... i want to share a problem that i got stuck with.. actually i have implemented problem 10 with loops and it works perfectly for small numbers .... takes upto 350 seconds for numbers upto 20000.... but after that... if i increase zeros i.e 200000 or 2000000(which is asked for) ..it keeps on executing.... nd is takin too much time and even after an hour it doesnt give out any result.... is there any other way to approach this problem??

[RishadanPort]

Have a read through 010 in the search field, and see if the question has already been answered.

There is for sure a better approach to solving the problem.

If you had done some of the previous prime problems -- Project Euler gives you a tutorial on how to find primes more efficiently. So I recommend you do those first before this one.