CODEWITHSUNDEEP
pythonpython-3.xprimes
chicken4thewin
chicken4thewin

Reputation: 1

Trying to make a Python 3 prime number generator

As the title suggests, I am attempting to make a Python 3-powered prime number generator and I can't get it to work.

Here is the code:

import random
def main():
    d=1
    x=random.randint
    while True:
        d=d+1
        if isinstance(x/d, int)==True:
            print (x)
        else: main()
main()

and the error:

Traceback (most recent call last):
  File "/media/mint/casper-rw/ProjectsOrWork/Python/PrimeIdle.py", line 10, in <module>
    main()
  File "/media/mint/casper-rw/ProjectsOrWork/Python/PrimeIdle.py", line 7, in main
    if isinstance(x/d, int)==True:
TypeError: unsupported operand type(s) for /: 'method' and 'int'

Upvotes: 0

Views: 277

Answers (2)

smci
smci

Reputation: 33960

Code is at bottom, but try to code your own based on the following suggestions, that's more educational for you:

  1. x = random.randint is not actually calling randint()
  2. You want to keep generating integer candidates and testing for primality. You should do this in a while-loop, not by recursing into main() every single time your candidate tests composite. That would cause unbounded stack growth and eventually overflow. (Never make a recursive call if you know you won't return from it). Also, you can't easily return from a very deep chain of recursion... you're kludging by using print(x) to sidestep that.
  3. For all those reasons, and good decomposition, partition this into a generator called generate_divisor() and a predicate function is_prime() (that returns True/False).
  4. Your main loop: here's how to make it non-recursive, and turn it into a while loop. For any integer x, you only need to test divisibility by (prime) divisors up to floor(sqrt(x)). If it isn't divisible by any of those divisors, it's prime, so is_prime() falls-through and returns True.
  5. Your test for divisibility: if (isinstance(x/d, int)==True) is bad, beware truncation errors on large x/d, use if (x%d == 0) to test for divisibility instead.
  6. Minor: you can easily get 60% performance boost on your prime sieve by observing that for d>5, primes can only end in 1,3,7 or 9. Hence don't do d = d+1 (or d += 1), you're generating lots of composite divisors and diminishing few primes. (Indeed you're generating tons of composite divisors like 27 or 51, then testing divisibility by those, which is a total waste of time, since you already tested divisibility by 3 and 17.)

.

import random
from math import sqrt, floor

def generate_prime_candidate():
    """Generator to generate random prime candidate"""
    yield random.randint() # probably do randint(2, 2**32 -1). You decide.

def find_random_prime():
    x = generate_prime_candidate()
    while not is_prime(x):
        x = generate_prime_candidate()
    # Found one!
    print(x)
    return x

def is_prime(x):  # normally we call integers n, floats x, but whatever...
    for d in generate_divisors(floor(sqrt(x))): # only search up to sqrt(x)
        if x%d == 0:
            return False # x is composite - d is a divisor
        return True  # x is prime

def generate_divisors(dmax):
    """Generate divisors, up to a limit. We exclude numbers easily known to be composite: residue 0,2,4,5,6,8 modulo 10"""
    yield 2
    yield 3
    yield 5 # now for d>5, exclude them by residue
    d = 7
    while d<dmax:
      while (d%10) == 5: # d easily known to be composite
        d += 2 # in fact we only need to test [0,2,4,6,8] not 5, since d+=2 is skipping residue 5 anyway
      yield d

Upvotes: 2

jonrsharpe
jonrsharpe

Reputation: 122086

x=random.randint

doesn't assign a random integer to x, it assigns the randint function. You should do:

x = random.randint(min, max)

However, that is the least of your problems - your prime test won't work, that isn't actually a generator function and you pick a new random number on each recursive call.

Upvotes: 1

Related Questions