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.
- Create a list containing integers from 2 to N.
- Remove all multiples of 2 from the list.
- Repeat the same process for the next remaining number. (In other words, remove all multiples of the current number)
- Repeat this until all numbers up to N have been processed.
- 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:
- 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.
- Since 0 and 1 are not prime numbers, these two indices are set to False.
- 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.
- 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: