## Problem 007

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

### Problem 007

Find the 10001st prime.
Calculate the sum of all primes below 2 million.
I know better than to ask for solutions, but I don't have a clue how to start. Can someone give me a hint as to how to solve these?

fish
There are 10 kinds of people in the world: those who understand binary, those who don't, and those who mistake it for trinary.

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Hint request

1. Write a function to test if a number is prime.
2. Think how you can speed up your test.
3. Think about how this function helps you solve the problems.
4. ?
5. Profit!!!
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

### Re: Hint request

A function to test if a number is prime - I seem to remember something about Fermat's Little Theorem, so I'll look that up and play around with that.
There are 10 kinds of people in the world: those who understand binary, those who don't, and those who mistake it for trinary.

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Hint request

I thought of something simpler. But sooner or later, Fermat's theorem will be very useful.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

euler
Posts: 3000
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

### Re: Hint request

fish613 wrote:I know better than to ask for solutions, but I don't have a clue how to start. Can someone give me a hint as to how to solve these?
For this problem (and with other problems relating to primes) look up the Sieve of Eratosthenes.

impudens simia et macrologus profundus fabulae

fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

### Re: Hint request

The Sieve of Eratosthenes I've heard of before, but I felt there might be better ways to find primes. Plus I'm not sure how to code it except for an arbitrarily large array, crossing off numbers as I go... and I can't help feeling I'm missing a neater way. Thanks for the advice, though.
There are 10 kinds of people in the world: those who understand binary, those who don't, and those who mistake it for trinary.

ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 9:57 am

### Re: Hint request

daniel.is.fischer wrote:... sooner or later, Fermat's [little] theorem will be very useful.
As will Fermat's Last Theorem, too, for PE #[censored] published earlier this year!
!647 = &8FDF4C

fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

### Re: Hint request

Problem 7 solved! Sum of primes below 2m calculated correctly.
As so often happens to me, I had a correct algorithm within about half an hour (thanks to all for tips and pm's on that), and spent about 2 hours changing the variable type to display the answer correctly...
I'll get to work on one of the others now.
There are 10 kinds of people in the world: those who understand binary, those who don't, and those who mistake it for trinary.

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Hint request

Regarding variable types: do not ever use floats unless you are completely, absolutely and utterly sure that you need them. And use doubles sparingly, too. Your friend is long long (or __int64, if you're on a funny platform). int may be faster, but it overflows too often.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

rayfil
Posts: 1400
Joined: Sun Mar 26, 2006 4:30 am
Contact:

### Re: Hint request

do not ever use floats unless you are completely, absolutely and utterly sure that you need them
Unless you are VERY familiar with the float format AND you really know what you're doing.
When you assume something, you risk being wrong half the time.

ThomasH
Posts: 117
Joined: Sun Mar 26, 2006 7:41 am
Location: Berlin, Germany

### Re: Hint request

rayfil wrote:Unless you are VERY familiar with the float format AND you really know what you're doing.
Thats funny: I do use extended type variables often. The reason is, that my compiler is poor in int64 overflow checking.
The extended type and the int64 type do have the same number of significant digits.

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Hint request

I referred to the type float, usually 32 bits. I think Raymond did, too. That one bites more often than not. Double (64 bits, 53 for the mantissa) and extended are okay if you know what to avoid.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

rayfil
Posts: 1400
Joined: Sun Mar 26, 2006 4:30 am
Contact:

### Re: Hint request

that my compiler is poor in int64 overflow checking.
For those following this thread who may not yet be aware of it, compilers alone do not check for 64-bit overflow of extended double precision floats. You need additional code and you can do it in several ways.
The easiest is probably to precompute 265 and store it as a float (80-bit variable) which you use to compare your other extended double precision floats for overflow.
When you assume something, you risk being wrong half the time.

fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

### Re: Hint request

I have now solved problem 7 as well. This time, it didn't take me ages to get the variable type right. I ought to know better than to try and use the Prime Number Theorem to try and predict an upper bound to sieve up to. When I increased the bound I got the right answer.
That means I have now answered all the questions I started this thread for help with. Which is not bad going.
Thanks all!
There are 10 kinds of people in the world: those who understand binary, those who don't, and those who mistake it for trinary.

benwr
Posts: 1
Joined: Sun Nov 09, 2008 8:41 pm

### Problem 7

I'm not sure how much of my solution I can post here, but suffice it to say that I was sure that my solution was correct, and then I looked it up and now i'm doubly sure. Problem 7 does not accept the correct answer. Or any answer that could be created by mistakenly using 1 as the first prime or anything like that. I always get the "your answer appears to be incorrect" error. I know it isn't an issue with every problem or with my account not being able to solve any problems, because to test it I solved problem 8.

hk
Posts: 10161
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 7 Incorrect Answer

I checked it. Problem 7 accepts the correct answer. So you are trying an incorrect answer.

hk
Posts: 10161
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 7 Incorrect Answer

yashkochar
Posts: 7
Joined: Tue May 12, 2009 3:17 pm

### Re: Problem 007

Hi, I am a new member and this is my first post. I concerns the solution of problem 7 and I thought instead of starting a new thread I will just post it here.
I was able to solve the problem. However after going though the "suggested" solution (which shows up as a pdf file link) and the solutions posted on the forum I observed that the most of the people have not used [snip spoiler]
I wanted to know how does this method compare to other posted esp. where you check every other "selected" number to see whether it's prime or not ?
Last edited by daniel.is.fischer on Tue May 12, 2009 6:02 pm, edited 1 time in total.
Reason: Remove spoiler

daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

### Re: Problem 007

I edited your post because it contained too direct references, we'd rather that people find them on their own (there's more fun in problem solving that way, we believe).

Your method is mentioned at the top of the pdf because it is far superior. However, we chose to present a fairly efficient version of the naive approach because
a) it doesn't involve any 'advanced' theory, which we deemed more appropriate in later pdfs
b) it's still much better than what many people used, but close enough to see and understand the inefficiencies.
If you put yourself in the place of somebody who used the algorithm of the second poster (and many more), probably the superior method would be too much to understand yet, but the version in the pdf should be okay.

Re comparison of the methods, you could test that yourself, the method you mentioned will be vastly superior (though if you want e.g. the 10-millionth prime, other methods would be superior to that).
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

yashkochar
Posts: 7
Joined: Tue May 12, 2009 3:17 pm