How to Optimize Prime Number Printing in Python for Accurate Results?

Printing Series of Prime Numbers in Python

Identifying prime numbers is a fundamental concept in mathematics and programming. A prime number is an integer greater than 1 that is not a product of two smaller integers. The following Python code aims to print a series of prime numbers from 1 to 100.

Code and Issue

One common approach to finding prime numbers is to iterate through numbers from 2 to n. For each number, check if it is divisible by any number between 2 and itself (excluding 1). If it is divisible, it is not a prime number; otherwise, it is.

Consider the following code intended to print prime numbers between 1 and 100:

<code class="python">for num in range(1, 101):
    for i in range(2, num):
        if num % i == 0:
            break
        else:
            print(num)
            break</code>

However, this code encounters an issue where odd numbers are printed instead of primes. The flaw arises because the outer loop iterates not only over prime numbers but also composite numbers (multiples of other numbers). Consequently, the condition if num % i != 0 becomes true for odd composite numbers like 9, leading to the erroneous printing of all odd numbers.

Solution and Optimization

To correct this, we must modify the code to explicitly check for prime numbers. Here's the revised version:

<code class="python">for num in range(2, 101):  # Start at 2 as 1 is not prime
    prime = True
    for i in range(2, num):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

In this code, we introduce a boolean variable prime, initially set to True. We then check each number between 2 and num-1 (excluding num) using the inner loop. If num is divisible by any number i, we set prime to False, indicating that it is not prime. After the inner loop, if prime remains True, we print num.

This code accurately identifies prime numbers within the specified range. However, it can be further optimized by only checking divisors up to the square root of num. This is because any factor greater than the square root would have a corresponding factor less than the square root.

Here's the optimized version:

<code class="python">for num in range(2, 101):
    prime = True
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

By using these tweaks, the code effectively prints the series of prime numbers between 1 and 100.

The above is the detailed content of How to Optimize Prime Number Printing in Python for Accurate Results?. For more information, please follow other related articles on the PHP Chinese website!