Chapter 24: Prime Number Generation Methods in Python

Prime numbers are fundamental in mathematics and have many applications in computer science and cryptography. In this chapter, we explore six different methods to generate prime numbers up to a given limit using Python.

Method 1: Brute Force Method

def is_prime(num):

    if num <= 1:

        return False

    for i in range(2, num):

        if num % i == 0:

            return False

    return True

def prime_generator(limit):

    primes = []

    for num in range(2, limit + 1):

        if is_prime(num):

            primes.append(num)

    return primes        

Method 2: Optimized Brute Force Method

def is_prime(num):

    if num <= 1:

        return False

    if num == 2:

        return True

    if num % 2 == 0:

        return False

    for i in range(3, int(num ** 0.5) + 1, 2):

        if num % i == 0:

            return False

    return True

def prime_generator(limit):

    if limit < 2:

        return []

    primes = [2]

    for num in range(3, limit + 1, 2):

        if is_prime(num):

            primes.append(num)

    return primes        

Method 3: Sieve of Eratosthenes

def sieve_eratosthenes(limit):

    sieve = [True] * (limit + 1)

    sieve[0] = sieve[1] = False

    primes = []

    for num in range(2, int(limit ** 0.5) + 1):

        if sieve[num]:

            for multiple in range(num * num, limit + 1, num):

                sieve[multiple] = False

    for num in range(2, limit + 1):

        if sieve[num]:

            primes.append(num)

    return primes        

Method 4: Trial Division with Improved Optimization

def trial_division_optimized(limit):

    if limit < 2:

        return []

    

    def is_prime(num, primes):

        for prime in primes:

            if prime * prime > num:

                break

            if num % prime == 0:

                return False

        return True

    

    primes = [2]

    for num in range(3, limit + 1, 2):

        if is_prime(num, primes):

            primes.append(num)

    return primes        

Method 5: Using SymPy Library

from sympy import primerange

def generate_primes_sympy(limit):

    return list(primerange(2, limit + 1))        

Method 6: Using a Generator Function

def prime_generator(limit):
    primes = [2] + [num for num in range(3, limit + 1, 2) if all(num % prime != 0 for prime in primes)]
    return primes        

You can run each of these methods to generate prime numbers and choose the one that best suits your needs. Prime numbers play a crucial role in various algorithms and mathematical concepts, making them an important topic to explore in Python.