Python: How to calculate prime numbers

Python: How to make generator of prime numbers

How to calculate prime numbers in Python by function and generator

Prime numbers it is a numbers which you can divide to 1 and to itself only. For example, 1, 2, 3, 5, 7 – are prime numbers. 4 not a prime number, because 4%2==0

There are few mathematical formulas, how to calculate prime numbers, but we will make simple generator without these mathematical equations. We will use the fact, that for every number (N) we need to check remainder of the division for every numbers from 2 till sqrt(N)+1 and if we will not find any – then it is Prime number

We will make this function as a generator for list and simple function. The difference will be only in the way of calling this function.

Python generator of prime numbers

This is a generator, which will return next prime number after each call. We will make a call with lambda function via itertools.takewhile() and send all data to list


import itertools

N = int(input("get max integer: "))
def primes_g():
    prm = 2                                    # start to check divider from 2
    while True:                                # work indefinite
        isprime = True                         # think that this number is prime
        for x in range(2, int(prm ** 0.5) + 1):# check all dividers to sqrt(prm)+1
            if prm % x == 0:                   # if it is divider
                isprime = False                # then refuse this number
                break                          # and go to another one
        if isprime:                            # if it is prime
            yield prm                          # retrun it and wait till next call
        prm += 1                               # increase test numbers and continue search

print(list(itertools.takewhile(lambda x : x <= N, primes_g())))

This will give for example:
get max integer: 67
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

We can keep all calculated prime numbers in the list, and then use them for further prime tests to make it work faster like function below.

Python function for prime numbers

This function is called once and it calculate full list of prime numbers between 2 and max input integer.


N = int(input("get max integer: "))
def primes_f(N):
'''function for prime number calculations
   It take N - max number in the list and
   then generate all numbers in the range [2, N]
'''
    prime = []                        # list of calculated prime numbers
    for x in range(2, N + 1):         # We check all numbers in range [2, N]
        max_test = int(x ** 0.5) + 1  # max value for check for remainder of the division
        isprime = True                # let's say that this number is PRIME untill refute it
        for test in prime:            # check only numbers from prime list
            if test > max_test:       # which less than max test value
                break
            if x % test == 0:         # if reminder of the division is ZERO
                isprime = False       # then is not PRIME 
                break
        if isprime:                   # if the x - PRIME
            prime.append(x)           # append it
    return prime

print( "primes: ", primes_f(N) )

This will produce:
get max integer: 55
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

Published: 2021-10-07 06:25:31
Updated: 2021-10-07 06:27:52