Problem 007

[fish613]

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

[daniel.is.fischer]

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

[fish613]

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.

[daniel.is.fischer]

I thought of something simpler. But sooner or later, Fermat's theorem will be very useful.

[euler]

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.

[fish613]

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.

[ed_r]

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

[fish613]

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.

[daniel.is.fischer]

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.

[rayfil]

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.

[ThomasH]

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]

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.

[rayfil]

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 2⁶⁵ and store it as a float (80-bit variable) which you use to compare your other extended double precision floats for overflow.

[fish613]

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!

[benwr]

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]

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.

[hk]

I PM'ed you my answer to your PM.

[yashkochar]

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 ?

[daniel.is.fischer]

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-million^th prime, other methods would be superior to that).

[yashkochar]

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