Optimization and Implementation of Prime Number Sequence Generation in Python

Introduction

Prime numbers hold significant importance in computer science and mathematics, with wide applications in cryptography, hash functions, and other domains. Generating prime number sequences in Python is a common programming exercise, but implementing efficient algorithms requires deep understanding of number theory and programming optimization techniques.

Problem Analysis

The main issue with the original code lies in logical errors: the inner loop prints the result and breaks upon encountering the first non-divisor, incorrectly identifying all odd numbers as primes. Proper prime identification requires checking all possible divisors.

for num in range(1, 101):
    for i in range(2, num):
        if num % i == 0:
            break
        else:
            print(num)
            break

Basic Solution

Using a boolean flag to track prime status is the most intuitive approach. For each number, we assume it's prime until finding a factor that divides it.

for num in range(2, 101):
    prime = True
    for i in range(2, num):
        if num % i == 0:
            prime = False
            break
    if prime:
        print(num)

Pythonic Optimization

Leveraging Python's built-in all() function makes the code more concise and readable. The all() function checks if all elements in an iterable are true.

for num in range(2, 101):
    if all(num % i != 0 for i in range(2, num)):
        print(num)

Mathematical Optimization: Square Root Limit

According to number theory principles, if a number is composite, it must have a factor less than or equal to its square root. Therefore, we only need to check up to int(math.sqrt(num)) + 1.

import math
for num in range(2, 101):
    if all(num % i != 0 for i in range(2, int(math.sqrt(num)) + 1)):
        print(num)

Further Optimization: Checking Only Odd Numbers

All primes except 2 are odd numbers, so we can skip all even candidates and check only odd numbers.

import math
print(2)
for num in range(3, 101, 2):
    if all(num % i != 0 for i in range(3, int(math.sqrt(num)) + 1, 2)):
        print(num)

Advanced Algorithm: Sieve of Eratosthenes

For large-scale prime generation, the Sieve of Eratosthenes is one of the most efficient methods. This algorithm progressively sieves out primes by marking multiples.

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    for p in range(2, n + 1):
        if sieve[p]:
            print(p)
            for i in range(p * p, n + 1, p):
                sieve[i] = False

Performance Comparison

Benchmark tests show significant performance differences when generating primes up to 1,000,000: basic trial division takes 272 seconds, while the optimized sieve method requires only 1.12 seconds. This highlights the importance of algorithm selection for efficiency.

Practical Applications

In practical programming, algorithm choice should depend on specific requirements. For small ranges (e.g., 1-100), simple methods suffice; for large ranges, sieve methods are preferable. Python's generator features can further optimize memory usage.

Conclusion

Through progressive optimization, we've evolved from logically flawed code to efficient prime generation algorithms. Understanding mathematical principles and Python features is key to implementing high-performance code. Developers should balance code simplicity, readability, and execution efficiency according to specific scenarios.