C++ Coding Test Course, Finding Prime Numbers

Algorithms are one of the key concepts in computer science and are particularly important in solving programming problems.
In this course, we will discuss the problem of ‘finding prime numbers’ and explain the algorithm and C++ code to solve it in detail.
A prime number is a natural number that can only be divided by 1 and itself, and it is one of the fundamental concepts in mathematics.
However, there are various approaches to solving this problem, each with different time complexities.

Problem Description

Given an integer N, write a program to find all prime numbers from 1 to N.
A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Input

The first line contains a natural number N (1 ≤ N ≤ 10^6).

Output

Print all prime numbers from 1 to N, one per line.

Example

Input:
    10

    Output:
    2
    3
    5
    7
    

Algorithm Approach

There are several methods to find prime numbers, but here we will use the classical method known as the ‘Sieve of Eratosthenes’.
This method can efficiently and relatively simply find prime numbers.
The Sieve of Eratosthenes works through the following procedure.

1. List all numbers from 1 to N.
2. Starting from 2, remove all multiples of that number.
3. Repeat the above process for the next remaining number.
4. Consider the remaining numbers as primes and output them.

Time Complexity

The Sieve of Eratosthenes algorithm has a time complexity of about O(N log log N).
It becomes more efficient as N increases, ensuring fast performance even for N = 10^6.

C++ Code

Below is the C++ code that implements the above algorithm.
Comments will be added to each step to aid understanding.

#include 
#include 
using namespace std;

int main() {
    int N;
    cin >> N; // Accept input from the user.

    // Create a vector of size N+1 and initialize all values to true.
    vector isPrime(N + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime.

    // Iterate from 2 to the square root of N.
    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) { // If i is prime,
            for (int j = i * i; j <= N; j += i) {
                isPrime[j] = false; // Multiples of i are not prime.
            }
        }
    }

    // Output the results.
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            cout << i << "\n"; // Print if it is prime.
        }
    }

    return 0;
}
    

Code Explanation

- #include and #include :
Include C++ input, output, and vector libraries.
- int N;: Declare an integer variable to hold user input.
- vector isPrime(N + 1, true);:
Declare a vector to store the primality of numbers up to N,
initializing all values to true.
(0 and 1 are not primes, so set separately)
- for (int i = 2; i * i <= N; i++):
Start from 2 and iterate up to the square root of N to find primes.
- The inner for (int j = i * i; j <= N; j += i) loop removes multiples of i.
- Finally, output all indices where isPrime[i] is true.

Conclusion

In this course, we introduced an algorithm to solve the problem of finding prime numbers and implemented it in C++. The Sieve of Eratosthenes is an efficient method for finding primes, and it is a common question in coding tests.
Familiarize yourself with the algorithm and code to confidently tackle coding tests!