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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
fish613
Posts: 15
Joined: Wed Jan 23, 2008 11:35 am

Problem 007

Post by fish613 » Mon May 05, 2008 5:26 pm

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?

Thanks in advance,
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.

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

Re: Hint request

Post by daniel.is.fischer » Mon May 05, 2008 5:37 pm

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ètes sont là.

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

Re: Hint request

Post by fish613 » Mon May 05, 2008 7:55 pm

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.

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

Re: Hint request

Post by daniel.is.fischer » Tue May 06, 2008 1:08 am

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ètes sont là.

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

Re: Hint request

Post by euler » Tue May 06, 2008 6:57 am

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. :wink:
Image
impudens simia et macrologus profundus fabulae

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

Re: Hint request

Post by fish613 » Tue May 06, 2008 11:46 am

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.

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

Re: Hint request

Post by ed_r » Tue May 06, 2008 6:33 pm

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! :D
!647 = &8FDF4C

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

Re: Hint request

Post by fish613 » Tue May 06, 2008 8:50 pm

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.

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

Re: Hint request

Post by daniel.is.fischer » Tue May 06, 2008 9:03 pm

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ètes sont là.

User avatar
rayfil
Administrator
Posts: 1400
Joined: Sun Mar 26, 2006 4:30 am
Location: Ontario, Canada
Contact:

Re: Hint request

Post by rayfil » Wed May 07, 2008 4:09 am

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. :) :) :lol:
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

Post by ThomasH » Wed May 07, 2008 1:46 pm

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.

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

Re: Hint request

Post by daniel.is.fischer » Wed May 07, 2008 2:17 pm

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ètes sont là.

User avatar
rayfil
Administrator
Posts: 1400
Joined: Sun Mar 26, 2006 4:30 am
Location: Ontario, Canada
Contact:

Re: Hint request

Post by rayfil » Thu May 08, 2008 12:37 am

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

Post by fish613 » Fri May 09, 2008 5:14 pm

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

Post by benwr » Sun Nov 09, 2008 9:01 pm

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.

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

Re: Problem 7 Incorrect Answer

Post by hk » Sun Nov 09, 2008 9:10 pm

I checked it. Problem 7 accepts the correct answer. So you are trying an incorrect answer.
You can PM me your answer and how you found it.
Image

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

Re: Problem 7 Incorrect Answer

Post by hk » Sun Nov 09, 2008 9:52 pm

I PM'ed you my answer to your PM.
Image

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

Re: Problem 007

Post by yashkochar » Tue May 12, 2009 3:35 pm

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

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

Re: Problem 007

Post by daniel.is.fischer » Tue May 12, 2009 6:47 pm

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ètes sont là.

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

Re: Problem 007

Post by yashkochar » Wed May 13, 2009 3:32 am

thank you for the reply.
i will be careful next time to not post hints which make the solution evident.

Post Reply