C# Coding Test Course, Finding Amazing Prime Numbers

In today’s software development environment, coding tests have become an important factor.
Companies present various problems to assess candidates’ algorithmic thinking and problem-solving skills.
In this blog, we will solve a coding test problem on the topic of finding interesting prime numbers.

Problem Description

Write a program to find and print all prime numbers less than or equal to the given integer N.
A prime number is a natural number that is divisible only by 1 and itself,
meaning it has no divisors other than 1 and itself among natural numbers greater than or equal to 2.

Input

An integer N is given in the first line. (2 <= N <= 1000000)

Output

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

Approach to the Problem

The most common method to find prime numbers is to use the Sieve of Eratosthenes.
This algorithm is efficient and can be used even when N is large.
Using the Sieve of Eratosthenes, prime numbers can be found in the following order:

List all numbers from 2 to N.
Starting from 2, remove all multiples of that number.
Select the smallest remaining number and remove its multiples in the same manner.
Repeat this process for numbers less than the square root of N.
All remaining numbers are prime.

C# Code Implementation

Below is the C# code that implements the above algorithm:

        
        using System;
        using System.Collections.Generic;

        class Program {
            static void Main(string[] args) {
                int N = int.Parse(Console.ReadLine());
                bool[] isPrime = new bool[N + 1];
                
                for (int i = 2; i <= N; i++) {
                    isPrime[i] = true; // Initialize all numbers as prime
                }

                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; // Mark multiples of i as non-prime
                        }
                    }
                }

                for (int i = 2; i <= N; i++) {
                    if (isPrime[i]) {
                        Console.WriteLine(i); // Print prime numbers
                    }
                }
            }
        }

Code Explanation

The above code implements the Sieve of Eratosthenes algorithm using C#.
Let’s go through each line in detail.

using System;: Adds the System namespace in C#.
using System.Collections.Generic;: Necessary for using collections like lists.
int N = int.Parse(Console.ReadLine());: Reads input from the user and saves it in N.
bool[] isPrime = new bool[N + 1];: Creates an array to store whether each number from 0 to N is prime.
for (int i = 2; i <= N; i++) { isPrime[i] = true; }: Initializes all numbers as prime.
for (int i = 2; i * i <= N; i++) { … }: Finds primes by iterating up to the square root of N.
if (isPrime[i]) { … }: If i is prime, marks all its multiples as non-prime.
for (int i = 2; i <= N; i++) { if (isPrime[i]) { Console.WriteLine(i); }}: Finally prints all remaining prime numbers.

Efficiency

The Sieve of Eratosthenes algorithm has a time complexity of O(N log log N) and
a space complexity of O(N). Therefore, it can find primes quickly even for large numbers like N = 1,000,000.

Conclusion

In this post, we explored how to find prime numbers using the Sieve of Eratosthenes algorithm in C#.
Problem-solving skills in algorithms are very important not only for coding tests but also for actual development,
so it is essential to strengthen your skills through continuous learning and practice.
In the next post, we will expand our algorithmic thinking through a variety of problems.