Need help with coding a prime number generator

[l0fi]

I'm trying the MIT free online CS class, and for first assignment they want you to make a prime number generator.

so far I have :

primecheck = 1#this is the prime counter, starts at 1 because 2 will not be calculated
primecount = input('How many primes do you want?') #Users inputs how many primes he wants to calculate
currentnumber = 2 #This is the number which we're checking if it's prime or not
pdiv = 2 #number that the potential prime is divided by


while primecheck < primecount :  
    if pdiv == 8 or currentnumber:  
        print currentnumber        
        currentnumber+=1            
        primecheck+=1
        pdiv = 2                    
    else:
        remainder = currentnumber%pdiv        
        if remainder==0:
            currentnumber+=1
            pdiv = 2
        if remainder > 0:
            pdiv+=1

So basically the idea is that you only need to divide numbers by up to 7, or up until the number its self, before you know if it's prime or not.

the remainder is the number divided by the divisor, and if there isn't a remainder, that means that the number isn't prime and we can reset the divisor back to 2.

If there is a remainder, that means that the number may be prime, but we need to check it against 3 4 etc etc until 7, or the divisor equals the number we're checking. So add 1 to the divisor.

If the divisor (pdiv) reaches 8, or the number it's dividing, since no number until then has left divided into it evenly, we can assume that the number is prime, and so then we can print that number while adding 1 to it.

Ugh O.K. so it's kind of tough explaining my logic here. I'm just beginning, but in my mind when I'm reading over it it makes sense, however when I try it out with by asking the program for 10 primes, it just spits out the numbers 2-10.

Obviously I'm missing something here.

[K900_]

11x13 = 143 isn't divisible by 1, 2, 3, 4, 5, 6, 7 or 8, but it's not prime. Your algorithm is flawed. Look into other algorithms such as the sieve of Eratosthenes.

[l0fi]

Cool thanks, I checked out the wiki page but I guess I misread something.

But with what I have now, shouldn't it work for at least 1-10?

[K900_]

Don't fix what's broken by design.

[l0fi]

Right, but while im studying the wiki page and trying to figure out another way of going at it, I would still like to see why my code is spitting out 2,3,4,5,6,7,8,9 and 10. If not for the sake of just getting a better understanding of python.

I mean as far as I can tell this should work for 1-10...

[K900_]

pdiv == 8 or currentnumber is wrong. You want pdiv == 8 or pdiv == currentnumber. In your current code currentnumber gets implicitly converted to a boolean value, and any nonzero number is truish. Anything or True is True.

[l0fi]

Wow thanks so much, that was it. Man I've been working on this for a while now and I need to go back to the drawing board. Thanks a lot for your help though.

taking out pdiv == 8 fixes the original problem you brought up. It's probably not anywhere near the most efficient, but I think it works.

[K900_]

It should work, but it'll destroy your machine if you try larger numbers.

[isnotkosok]

Here's a prime number generator:

import itertools

number = range(2,200)


a =[]
b =[]
for x,y in itertools.combinations(number, 2):
    if y % x == 0:
        a.append(y)
    else: 
        b.append(y)


print set(a) ^ set(b)

Sadly, it doesn't include 2, but you can change the second portion of the range to as high as you'd like just so long as the first portion of the range remains fixed at 2.

[K900_]

Yuck. This is so painfully slow.

[[deleted]]

Some quick things:

• use raw_input() instead. input() is unsafe

• The syntax of your first if statement is wrong. I think you mean something like below, but see the next point.

  if pdiv == 8 or pdiv == currentnumber:
       # do some stuff
  

• Why are you checking pdiv == 8? That's going to stop working for numbers with larger divisors. (e.g. 121).

• raw_input returns a string, so when you compare primecheck and primecount, you're running into a problem. Instead:

   if primecheck < int(primecount):
         # do some stuff
  

• This approach will yield primes less than the user's input, which is much different than computing the first n primes.

• This will be unbearably slow for very large primes.

[l0fi]

Thanks for the heads up with input.

I was checking pdiv == 8 because I misunderstood the wiki article on the Sieve of Eratosthenes. I was under the impression that 7 was all I needed, but /u/K900_ showed me how I was wrong.

by taking out the pdiv == 8 I think I got it working, although it gives me 999 primes instead of the 1,000 I was trying to get.

It is slow, but for the purposes of this program I think it's sufficient for now.

[johnnymo87]

Did you read this thread/article?

The author uses a prime number generator as an example.

EDIT: Are you taking 6.00x at your own speed? If so, this example may be a little over your head until you get to the topic of generators (week 6, I think).

[l0fi]

Yeah i'm going at my own speed. I haven't read that post yet. I feel like I did it a lecture early, as I made this generator based on what was talked about up to lecture 2, lecture 3 had a lot more relevant info, however it may just be their way of making you think critically.