Question

I have coded assignment 1, but am having problems with getting my "counter" to work. Here is my code using Fermats little theorem to determine primality;


x = 0
#x is going to be my counter, looking for 1000th prime
y = 1
#y will be the tested prime
while x < 1000 :
myint = (2**y-2)%y
#if myint is anything other than 0, it is not prime
if myint > 0:
y = y + 1
else :
y = y + 1
x = x + 1
print y - 1
This code successfully tests primality, but seems to have problems getting to the 1000th prime, making me think my counter is off... help?

Answer 1

here are my minor modifications, it looks like it is 19 off: x = 1
#x is going to be my counter, looking for 1000th prime
y = 2
#y will be the tested prime
while x < 1019 :
myint = (2**y-2)%y
#if myint is anything other than 0, it is not prime
if myint > 0:
y +=1
else :
y +=1
x +=1
print y-1

the 1000th prime is 7919 ( http://primes.utm.edu/lists/small/1000.txt) I'm not sure. Someone with more experience will probably understand it better than I.

Answer 2

So there is a problem with the formula somewhere:
The differences between the actual your your program are:
341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4369
4371
4681
5461
6601

so the problem isn't with the counter.

Answer 3

I have several observations or comments. First, any particular reason why you are using Fermat's Little Theorem rather than the standard method (i.e. test whether any other integer > 1 evenly
divides the candidate with 0 remainder)? The problem with FLT is that it is a one way theorem. It tells you that primes satisfy the property but so do other numbers which are not primes. I would use the standard test for primality and see if you can program that. Perhaps you have already done that. Secondly, how do you know that your program actually tests properly for primality? How about putting in a print statement (for debugging purposes) somewhere to see whether you are picking up the primes and only primes up to wherever it stops. Third, and this is the most important point. Looking at your program it's not clear what the logic or computational steps are. Can you write that down for us in plain language. It's always good to write down the steps of your program first in plain language.

Answer 4

I actually had all of the steps commented in, but the character limit on comments kept me from having them all in there haha. I used Fermats Little Theorem mostly because it seemed to be the quickest way to compute primality, however not having been in a math class in over 4 years I'm having less trouble wrapping my head around the code than I am with relearning mathematical formulas. I tested whether the prime calculations worked using a print statement and they seemed to be on target, though I had to head off to work before I could fully compare my chart to the chart given on the assignment. Now that I'm out I'll double check it and let you know if it's coming up gravy or not.

Answer 5

Just noticed arthur's comment; looks like I'll have to find a new way to calculate primes. Damn, thought I was onto something haha.

Answer 6

testprime = 14
# this is the test prime
y = 2
# this is the test number
# if any number divides evenly into the prime than 1, it is not prime
isprime = 0
# this is the default 'Is it prime?' setting that changes to 1 if it is
# prime and 2 if it is not
while y < testprime :
# this while statement keeps track of the testprime number, keeping it below
# the testprime since if they are equal it will always end in '1'
if isprime == 0 :
end = testprime%y
# end is the remainder value of testprime divided by y; looking for 0's
y = y + 1
# this series checks to see if isprime is still default, aka still checking
# on the primality of the number, therefore still adding 1 to y
if end > 0 :
isprime = 1
# this is the actual check to see if the end result of
# testprime and y is a float or not, if an int it will set
# isprime to 1; which means it is prime until proven otherwise
elif end == 0 :
isprime = 2
break
# this is the check that if it finds no remainders, will
# flag the number as not prime and break the if statement
# to keep from checking the rest of the numbers
else :
break
# this breaks the loop if any number is assigned to isprime
# other than 0
if isprime == 1 :
print "This number is Prime!"
elif isprime == 2 :
print "This number is NOT Prime!"
# these final functions check the 'isprime' setting and display whether it
# is prime or not to the user





This function seems to work for me quite well, does everything check out to you folks? All I have to do now is hook it up to a counter to get it to go to 1000... I hope.

Answer 7

I am using the simple method and I am having problems also getting to stop on the 1000th

Answer 8

Turns out I have created a very reliable odds and even calculator. Crap.

Answer 9

You can look at my implementation here http://meeplikesheep.wordpress.com/2011/12/24/assignment-1-revisited/
A more efficient way while still using the simple method would be to keep track of primes in a list, and check only primes as factors. But a little lazy to do it :)

Answer 10

To oneI3d: Since you are being able to generate primes. You need to count every time you generate a prime and stop when you get to 1000. The pseudo-code would look like:
1- Generate odds
2- Test prime condition for every odd generated
3- Every time you find a prime count
4- When your counter ==1000 the loop must stop so your test will be something like:
while counter<1000:
Generate next odd
Test odd as prime
If yes count+=1
Hints: don't forget to initialize counter, and that 3 is 3rd prime.

Answer 11

To Wardo: You are close, but your primality test does not work properly because you compare 'y' and 'testprime' before checking for testprime%y; only after you find that testprime%y==0 is that you should check the relationship between 'y' and 'testprime'. Try to look at the previous post to onel3d as well.

Answer 12

@Mike- Good points, but 3 is the 2nd prime.

Answer 13

I'm a bit past this problem now, but I enjoy seeing the different routes people took. I also tried using Fermi's little theorem at the start, but abandoned it as soon as I realized it returned non-primes. Here's the code I ended up with, if anyone cares to examine it:

count = 2
candidate = 3
countTarget = int(input("Generate which prime? "))

while countTarget > count:
candidate += 2
is_candidate = True
for factor in range(2,int(candidate**0.5)+1):
if candidate%factor == 0:
is_candidate = False
if is_candidate:
count += 1
print candidate

print candidate,"is prime number",countTarget

It lacks a way to handle non-integer user input (a habit I'm still trying to break out of). I was also ahead in the readings at the time and attempted this with a function, but that was almost too easy, and I forced myself to work it out with only the knowledge I would've had at the time of the assignment.

Answer 14

prime = int(raw_input('What prime numner would you like to find: '))
primeNumbers = (2,)
testNumber = 3
divisors = 0
while len(primeNumbers)<prime:
for i in range(2,testNumber-1):
if testNumber%i==0:
divisors = 1
break
if divisors==0:
primeNumbers = primeNumbers + (testNumber,)
testNumber = testNumber + 2
divisors = 0
print primeNumbers[-1]

Answer 15

@jrbearduga, the technique of using the length of a tuple of every determined prime for your conditional is interesting, but isn't that going to use up a lot of memory? If you're going to do it that way, it might be fun to take advantage of the tuple and throw in a "Find another?" prompt afterwards. If the request is a lesser prime than the first search, you could just print primeNumbers[n]. If it's a greater prime, continue the operation.

I do recommend restricting the range of numbers when testing for factors. There's never any reason to test above the square root of a candidate, since any factor ABOVE the root would have to be multiplied against a number BELOW it. This can save your program a lot of cycles.

Answer 16

Hmm, there are a lot of functions I'm seeing in here that would help me immensely, perhaps I'll watch lecture 3 and read a few more chapters in before tackling this (for instance, knowledge of the "range" function would have been nice to know before starting haha. I've generated a simpler method to check primes than my last code that basically checks to see if the prime / testnumber * testnumber = prime. Since I am only using integers, it stands to say that in a prime number none of the checks will equal the prime number. It works to the point that it can identify non-primes, however I'm getting an infinite loop when it finds a prime...

Answer 17

prime = 7
testnum = 2
isprime = 0
while isprime == 0 :
if testnum < prime :
remainder = prime / testnum
if remainder * testnum == prime :
isprime = 2
break
else :
if testnum < prime :
testnum = testnum + 1
elif testnum == prime :
isprime = 1
if isprime == 1:
print "This number is prime!"
else :
print "This number is not prime!"

The code I created on my lunch break today resulting in an infinite loop...

Answer 18

@wardo, I'm still interpreting your code, but I wonder if the 'break' is necessary. You've already reassigned isprime to something other than 0, so the loop should close on its own.

Also, you're testing elif testnum == prime within an if testnum < prime. You should look over the whole else clause. It contains that elif test that doesn't seem like it would ever be used, and also contains a redundant if testnum < prime, since judging by the indentation, it would only ever encounter that test after already determining testnum < prime from the first if.

...I'm still not used to talking about code, haha. Sorry if the flow of my writing is strange.

Answer 19

@Joshua D, isn't using a tuple for the first part the easiest way to complete the second part?

Answer 20

@jrbearduga, I'm not sure! 'Easy' is hard for me to quantify at this point. XD The second part was summing the logs of the primes, yeah? I think I declared a 'sum' variable and adjusted my code so that, whenever it discovered a prime, it added its log to the sum (sum += log(candidate), or sum = sum + log(candidate), however you want to write it).

Answer 21

@Josh, I looked at my code and I agree that I do not need the break or the elif, however it seems to still be computing non-primes and spitting out "This is not prime!" if I give it a non-prime number but rolling in an infinite loop if the number is prime... not sure where I'm going wrong.

Updated Code:

prime = 9
testnum = 2
isprime = 0
while isprime == 0 :
if testnum < prime :
remainder = prime / testnum
if remainder * testnum == prime :
isprime = 2
else :
if testnum < prime :
testnum = testnum + 1
else :
isprime = 1
if isprime == 1:
print "This number is prime!"
else :
print "This number is not prime!"

Answer 22

@wardo, ah, I see it now. Once your test completes and testnum +1 eventually makes testnum == prime, the loops breaks because you have no path for that condition to take. Defining isprime = 1 is only possible in your code after meeting your testnum < prime condition (which it never would if the values are finally equal).

Your program works if you reduce your entire else clause down to just testnum = testnum +1. Then, create a second, separate conditional just for the instance when testnum == prime, defining isprime = 1 at last. Or to illustrate, here is my modification of your code:


prime = 17
testnum = 2
isprime = 0
while isprime == 0:
if testnum < prime:
remainder = prime / testnum
if remainder * testnum == prime:
isprime = 2
else:
testnum = testnum + 1
if testnum == prime:
isprime = 1
if isprime == 1:
print "This number is prime!"
else :
print "This number is not prime!"

So your method of testing is right on track. It just didn't quite know how to get to the finish line.

Answer 23

Lately when programs are kicking my butt, I've taken to sitting in front of IDLE and working through the problem case line by line, following the path it would have to take. It's a completely unrealistic method for larger programs, I'm sure, but at this level, it might be a good way to find where the brick walls are. It was how I finally noticed that a prime number gets lost.

Also, it can be worth it, after killing an infinite loop (Ctrl-C), to type in your variable names to see where their values were at the time of the crash.

Answer 24

Also, the way I fixed your code isn't the only way to fix it. It was just the first way that was apparent to me. I can see one other trick to make your code work, and I'm sure there are several others. You got the test down, which is the hard part. Everything else is just grammar.

Answer 25

@Josh Thanks! I finally got it this morning. I literally was at work and had an "AHA!" moment and wrote the code down on a piece of paper plate and brought it home. Minus all of my comments my code ended up like this:

prime = 2
counter = 1
# this is the counter that will make it to 1000
while counter <= 1000 :
testnum = 2
isprime = 0
while isprime == 0 :
if testnum <= prime :
remainder = prime / testnum
if remainder * testnum == prime and testnum != prime :
isprime = 2
elif testnum == prime :
isprime = 1
else :
testnum = testnum + 1
if isprime == 1:
counter = counter + 1
prime = prime + 1
else :
prime = prime + 1
print prime - 1

You all have been a huge help through this first assignment! Thanks!

Answer 26

Your mistake is in the formula (2**y-2)/y remember operators precedence? (2**(y-2))/y
will do the right calculation for the prime.
look at this code:
# is a prime?
#
def isPrime(test_prime):
value_is_prime = int(test_prime)
counter = int(test_prime) - 1
current_counter = 2
calc = 1

if test_prime == 1 or test_prime == 2:
return test_prime

while current_counter < counter:
calc = calc * (test_prime % current_counter)
current_counter = current_counter + 1

if calc != 0:
return int(value_is_prime)
else:
return 0
#
# end def isPrime

# __Main Program__
print "\t\t\t The First 1,000 Primes\n"
counter = 0
seed = 1
while counter <= 1000:
if isPrime(seed) != 0:
if counter == 1000:
print "the 1,000th prime is ",
counter = counter + 1
print seed, "\t",

seed = seed + 1

Answer 27

@wardo, grats! I love the "AHA!" moments. XD Even when you see a hundred alternate solutions to a problem, it's why we wreck ourselves trying to figure it out our own way. It feels great when you finally 'get it'.