## 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
hk
Posts: 10158
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

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

coziroyc
Posts: 2
Joined: Wed Jul 20, 2011 1:36 pm

### Re: Problem 007

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

machine_easy2
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??

machine_easy2
Posts: 11
Joined: Tue Jul 12, 2011 6:23 am

### Re: Problem 007

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??
Better loop control.

mavritivs
Posts: 4
Joined: Fri Jun 01, 2012 3:03 am

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

mdean
Posts: 142
Joined: Tue Aug 02, 2011 1:05 am

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

mavritivs
Posts: 4
Joined: Fri Jun 01, 2012 3:03 am

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

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

### Re: Problem 007

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.
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
Posts: 6
Joined: Wed Nov 27, 2013 3:52 pm

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

LarryBlake
Posts: 100
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.