{"id":33832,"date":"2024-11-01T09:20:58","date_gmt":"2024-11-01T09:20:58","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33832"},"modified":"2024-11-01T10:55:53","modified_gmt":"2024-11-01T10:55:53","slug":"c-coding-test-course-finding-prime-numbers","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33832\/","title":{"rendered":"C# Coding Test Course, Finding Prime Numbers"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

Find all prime numbers less than or equal to the given natural number N<\/code>.<\/p>\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.<\/p>\n

Input<\/h2>\n

A natural number N<\/code> (2 \u2264 N \u2264 10,000,000)<\/p>\n

Output<\/h2>\n

Print all prime numbers less than or equal to N, one per line<\/p>\n

Example<\/h2>\n
Input:\n10\n\nOutput:\n2\n3\n5\n7\n<\/code><\/pre>\n
Problem Solving Strategy<\/h2>\n
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.<\/p>\n
The Sieve of Eratosthenes algorithm works as follows:<\/p>\n
    \n
  1. Create an array containing all numbers from 2 to N.<\/li>\n
  2. Since 2 is prime, remove all multiples of 2 from the array as they cannot be prime.<\/li>\n
  3. Next, select the first remaining prime number, which is 3, and remove all multiples of 3.<\/li>\n
  4. Repeat this process until the end of the array. The remaining numbers are primes.<\/li>\n<\/ol>\n
    C# Implementation<\/h2>\n
    Let’s implement a program to find prime numbers in C# using the above method:<\/p>\n
    using System;\n\nclass Program\n{\n    static void Main(string[] args)\n    {\n        \/\/ Get N from the user\n        Console.Write(\"Enter a natural number N (2 \u2264 N \u2264 10,000,000): \");\n        int N = int.Parse(Console.ReadLine());\n\n        \/\/ Initialize a vector array for prime checking\n        bool[] isPrime = new bool[N + 1];\n\n        \/\/ Initialize all numbers as prime\n        for (int i = 2; i <= N; i++)\n        {\n            isPrime[i] = true;\n        }\n\n        \/\/ Sieve of Eratosthenes algorithm\n        for (int i = 2; i * i <= N; i++)\n        {\n            if (isPrime[i])\n            {\n                \/\/ Set multiples of i to false\n                for (int j = i * i; j <= N; j += i)\n                {\n                    isPrime[j] = false;\n                }\n            }\n        }\n\n        \/\/ Print results\n        Console.WriteLine($\"The following are prime numbers less than or equal to {N}:\");\n        for (int i = 2; i <= N; i++)\n        {\n            if (isPrime[i])\n            {\n                Console.WriteLine(i);\n            }\n        }\n    }\n}\n<\/code><\/pre>\n
    Code Explanation<\/h2>\n