C# Coding Test Course, Finding Prime Numbers

Problem Description

Find all prime numbers less than or equal to the given natural number N.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, 13, 17, 19 are prime numbers.

Input

A natural number N (2 ≤ N ≤ 10,000,000)

Output

Print all prime numbers less than or equal to N, one per line

Example

Input:
10

Output:
2
3
5
7

Problem Solving Strategy

One of the most well-known algorithms for finding prime numbers is the Sieve of Eratosthenes. This algorithm helps efficiently find all prime numbers within a given range.

The Sieve of Eratosthenes algorithm works as follows:

1. Create an array containing all numbers from 2 to N.
2. Since 2 is prime, remove all multiples of 2 from the array as they cannot be prime.
3. Next, select the first remaining prime number, which is 3, and remove all multiples of 3.
4. Repeat this process until the end of the array. The remaining numbers are primes.

C# Implementation

Let’s implement a program to find prime numbers in C# using the above method:

using System;

class Program
{
    static void Main(string[] args)
    {
        // Get N from the user
        Console.Write("Enter a natural number N (2 ≤ N ≤ 10,000,000): ");
        int N = int.Parse(Console.ReadLine());

        // Initialize a vector array for prime checking
        bool[] isPrime = new bool[N + 1];

        // Initialize all numbers as prime
        for (int i = 2; i <= N; i++)
        {
            isPrime[i] = true;
        }

        // Sieve of Eratosthenes algorithm
        for (int i = 2; i * i <= N; i++)
        {
            if (isPrime[i])
            {
                // Set multiples of i to false
                for (int j = i * i; j <= N; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        // Print results
        Console.WriteLine($"The following are prime numbers less than or equal to {N}:");
        for (int i = 2; i <= N; i++)
        {
            if (isPrime[i])
            {
                Console.WriteLine(i);
            }
        }
    }
}

Code Explanation

• Getting Input: Requests the user to input N. Converts the received value to an integer.
• Initializing Prime Array: Creates a boolean array initialized to true, assuming all numbers up to N are prime.
• Implementing Sieve of Eratosthenes: Uses two nested loops to set non-prime numbers to false. The outer loop starts from 2, and the inner loop sets multiples of i to false.
• Outputting Results: Finally, finds indices in the array that are still true and outputs the corresponding prime numbers.

Complexity Analysis

The time complexity of this algorithm is O(n log log n) and its space complexity is O(n). This makes it very efficient for finding large ranges of prime numbers.

Conclusion

In this course, we introduced an algorithm for finding prime numbers and explained how to implement it using C#. The Sieve of Eratosthenes is a very efficient prime detection algorithm that often appears in actual coding tests. Understanding the concept of prime numbers and implementing the algorithm will greatly enhance your programming skills.