Problem 007
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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.
Re: Problem 007
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.
More often than not it turns out that people found the 1001st prime, while the 10001st prime is asked for.
Re: Problem 007
You're right. I found the 1001st prime. I thought I read the instructions carefully. Oops.

 Posts: 11
 Joined: Tue Jul 12, 2011 6:23 am
Re: Problem 007
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??
Any help??

 Posts: 11
 Joined: Tue Jul 12, 2011 6:23 am
Re: Problem 007
Better loop control.machine_easy2 wrote: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??
Re: Problem 007
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.
Thanks.
Re: Problem 007
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
Re: Problem 007
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.
Thanks a lot for that link, I do not know how I overlooked that section on wikipedia.
Re: Problem 007
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 timeconsuming full check in most cases.mavritivs wrote: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.
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.
Re: Problem 007
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
 Posts: 117
 Joined: Fri Jul 26, 2013 3:54 pm
 Contact:
Re: Problem 007
Beware, 341 is not a Carmichael number. Carmichael numbers are pseudo primes in any prime base.
The first Carmichael number is 561.
The first Carmichael number is 561.

 Posts: 98
 Joined: Sat Aug 29, 2009 7:49 pm
Re: Problem 007
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.