Problem 007

[hk]

We've heard that before.
More often than not it turns out that people found the 1001st prime, while the 10001st prime is asked for.

[coziroyc]

You're right. I found the 1001st prime. I thought I read the instructions carefully. Oops.

[machine_easy2]

I keep getting a few numbers passing through my sieve that are not prime. In my list of "the first 30 primes" I'm getting an incorrect 27 and 95....

Any help??

[machine_easy2]

I keep getting a few numbers passing through my sieve that are not prime. In my list of "the first 30 primes" I'm getting an incorrect 27 and 95....

Any help??

Better loop control.

[mavritivs]

I am using Fermat's Little Theorem for this, but I am getting an error. For prime #69, it lists "341". I double checked this with another script of mine to check for primality. It says 341 is not prime. Could anyone tell me what I am doing wrong or look at my code for mistakes? I really cannot seem to find one.

Thanks.

[mdean]

You probably shouldn't be posting how you attempt to solve the problem. I have a feeling you might find this relevant though: http://en.wikipedia.org/wiki/Fermat%27s ... eudoprimes

[mavritivs]

I only mention Fermat since it was already mentioned in the beginning of this thread.
Thanks a lot for that link, I do not know how I overlooked that section on wikipedia.

[thundre]

I am using Fermat's Little Theorem for this, but I am getting an error. For prime #69, it lists "341". I double checked this with another script of mine to check for primality. It says 341 is not prime. Could anyone tell me what I am doing wrong or look at my code for mistakes? I really cannot seem to find one.

Fermat's Little Theorem is more useful for proving which numbers are composite than which are prime. It can be used as a first check, so you can avoid the more time-consuming full check in most cases.

See http://en.wikipedia.org/wiki/Carmichael_number

341 = 11 * 31, so it is composite.

2 and all powers thereof are Fermat liars in base 341. But 3^341 % 341 = 168.

[pcworx]

Man I hope this isn't giving away too much on the solution, but seeing how there are several prime number problems I just wanted to verify one thing. Once your divisor is 1/2 of the potentialprime number there isn't any reason to keep dividing right? I mean let's say 101 is a prime, once your divisor test is up to 51 there is no point in going on up higher with your divisor because the result will be less than 2? I am new to math and programming so forgive me if I have done wrong....just a dumb American here.

[nicolas.patrois]

Beware, 341 is not a Carmichael number. Carmichael numbers are pseudo primes in any prime base.
The first Carmichael number is 561.

[LarryBlake]

pcworx, you're right that you don't need to test above half the number. You can actually stop testing sooner than that if you think about it a little further.

[Liquid25677]

I've been trying to solve this problem for some days but I can't seem to write a working code. I've seen people here saying to send a PM , anyone can help? I can't understand where I'm wrong.

[SaxTenor]

I've been trying to solve this problem for some days but I can't seem to write a working code. I've seen people here saying to send a PM , anyone can help? I can't understand where I'm wrong.

The Sieve of Eratosthenes may helps you.

[linkman8912]

I've made a sieve that works, but it doesn't print anything when I set the highest number to sieve to 46350 (I'm using c++.) I don't know if this number is something special in binary, or something related to the integer limit, but it doesn't seem like it. I know better than to post code, but please tell me if more details are needed, and I can pm them.

[Koder256]

This, I think is the most efficient code without using external modules

[Codes removed by Admin.
Please note that this forum is meant only for clarification of the problems. The proper place to post your solution is the discussion thread for this problem.]