Python Coding Test Course, Finding Prime Numbers

1. Problem Description

The task is to find all prime numbers that are less than or equal to a given number N. A prime number is an integer that has only two divisors: 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers.

Problem Definition

Write a program to find prime numbers that satisfy the following conditions.

        Function name: find_primes
        Input: Integer N (2 ≤ N ≤ 10^6)
        Output: Returns a list of all prime numbers less than or equal to N
    

2. Approach

One of the most commonly used methods to find prime numbers is an algorithm known as the ‘Sieve of Eratosthenes’. This algorithm is an efficient way to find all prime numbers within a given range, and it proceeds through the following steps.

  1. Create a list containing integers from 2 to N.
  2. Remove all multiples of 2 from the list.
  3. Repeat the same process for the next remaining number. (In other words, remove all multiples of the current number)
  4. Repeat this until all numbers up to N have been processed.
  5. The numbers that remain until the end are prime numbers.

3. Algorithm Implementation

Now, let’s implement the Sieve of Eratosthenes algorithm described above in Python. Below is the complete code.

def find_primes(N):
    # Exclude 0 and 1 as they are not prime numbers.
    if N < 2:
        return []
    
    # Initialize the list for finding primes
    sieve = [True] * (N + 1)  # Initialize all numbers as potential primes
    sieve[0], sieve[1] = False, False  # 0 and 1 are not primes

    for i in range(2, int(N**0.5) + 1):  # Proceed from 2 up to sqrt(N)
        if sieve[i]:  # If i is prime
            for j in range(i * i, N + 1, i):  # Set multiples of i to False
                sieve[j] = False

    # Create a list of primes
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

# Test
N = 100
print(find_primes(N))  # Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    

4. Code Explanation

The code works as follows:

  1. First, a list called 'sieve' is created, and an array of size N+1 is initialized to True. In this array, the index represents the numbers, and a value of True indicates that the corresponding number is prime.
  2. Since 0 and 1 are not prime numbers, these two indices are set to False.
  3. A loop is executed from 2 to sqrt(N). In this process, the current number i is checked for primality (sieve[i] is True). If it is prime, all multiples of i are marked as False.
  4. After all checks are completed, the indices that still have True values are collected into a list and returned as prime numbers.

5. Performance Analysis

The Sieve of Eratosthenes algorithm has a complexity of O(n log log n), which is quite efficient. Therefore, it can find prime numbers quickly even for the given condition of N ≤ 10^6.

6. Conclusion

The problem of finding prime numbers can be solved using various algorithms, but the Sieve of Eratosthenes is one of the most efficient and intuitive methods among them. By utilizing this algorithm, you can solve various problems, so be sure to master it!

7. Additional References

If you want to study more in-depth algorithms, the following resources are recommended: