Generating large prime numbers in python

Question

I can't seem to make random prime numbers using this code, please can someone help me?

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          prime = False
        else:
          prime = True


  return n

Chauffer

On each iteration of the for loop, you're ignoring what the earlier iterations told you by setting prime = False or prime = True without considering what prime used to be. – Gage

Answer 1

Imagine what happens if the last number in range(3, int(n**0.5), 2) is not an integer divisor of n:

if n % x ==0:
    prime = False # not this
else:
    prime = True # this

So even if all previous checks evaluated False, you call n a prime. The minimal change to your code to fix this is:

prime = prime and True # or 'prime &= True'

So if prime is already False, it remains False.

However, bear in mind that, for primality, if any of those checks is False n is not prime. You can use this and Python's and and all (which are evaluated lazily, i.e. don't keep checking once finding a False) to implement much more efficiently:

def rand_prime():
    while True:
        p = randint(10000, 100000)
        if (r % 2 != 0 and
            all(p % n != 0 for n in range(3, int(((p ** 0.5) + 1), 2))):
            return p

For even better performance, note that randrange incorporates a step argument, just like range, so you can skip all of the even numbers (which definitely aren't prime!):

def rand_prime():
    while True:
        p = randrange(10001, 100000, 2)
        if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)):
            return p

Note: sqrt(n) (from math) is, in my opinion, a little clearer to other, less-technical readers than n ** 0.5 (although it may or may not be more efficient).

Jacks

very nice answer. helpful – Ashleyashli

Answer 2

Correct logic, you are setting True when n % x ! = 0 for first time:

  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      prime = False
    else:
      prime = True

should be:

  prime = False
  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      break
  else: 
    prime = True

Read break and continue Statements, and else Clauses on Loops.

The shorter way of writing equivalent code will be (from @Steve Jesso):

prime = all(n % x != 0 for x in range(3, int(n**0.5), 2)

Ashleyashli

The OP only wants to return once a prime is found, not return False - it should loop to a new random number. – Jacks

The else of a for loop executes if the loop doesn't break, so you should set prime = True in there. But actually you can replace the whole thing with prime = all(n % x != 0 for x in range(3, int(n**0.5), 2). – Garrettgarrick

@SteveJessop Yes I corrected. also added your suggestion Thanks! – Ashleyashli

Answer 3

Take a look to the tabs: The else should refer to the whole for loop, not to the iF

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          break
      else:
          prime = True


  return n

Grivet

Considering that the loop doesn't even have a break in it, this is not a correct answer. – Gage

Answer 4

There're errors in your code:

1. Incorrect "else:"; you can't declare number being prime if a remainder is not 0; All the remaiders should be non-zeros
2. int(n*0.5) should be int(n*0.5 + 1) to prevent round-up errors

The possible solution is

def RandomPrime():
  while True:
    n = random.randint(10000, 100000)

    if n % 2 == 0:
      continue;

    prime = True;

    for x in range(3, int(n**0.5 + 1), 2):
      if n % x == 0:
        prime = False;

        break; 

    if prime: 
      return n

Springwood

Answer 5

Generating large random numbers over and over can cost a lot of time. For this reason I chose one random number, then incremented it until a prime number was found.

import random

def generate_big_prime(size:int):
    p = random.randrange(2 ** (size - 1), 2 ** size - 1)
    if p % 2 == 0:
        p += 1
    while not is_prime(p):
        p += 2
    return p

Where size is the number of bits desired and is_prime(n:int) is a primality test.

Since testing the primality can be very slow, again especially for large numbers, I would recommend the Miller-Rabin primality test for its efficiency.

Auerbach