Sieve of Eratosthenes

Get all prime number for the given number using Sieve of Eratosthenes algorithm

For example:

Input
8


Output
2, 3, 5, 7

Solution:


using System;
using System.Collections.Generic;

namespace Eratosthenes
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine("Enter a number:");
            var num1 = Convert.ToInt32(Console.ReadLine());

            var result = SieveOfEratosthenes(num1);

            Console.WriteLine($"List of prime number less then {num1}:");
            foreach (var i in result)
            {
                Console.WriteLine(i);
            }

            Console.ReadLine();
        }

        public static List<int> SieveOfEratosthenes(int n)
        {
            var prime = new bool[n + 1];
            var result = new List<int>();
            for (var i = 0; i < n; i++)
                prime[i] = true;

            for (var i = 2; i * i <= n; i++)
            {
                if (prime[i] != true) continue;
                for (var j = i * i; j <= n; j += i)
                    prime[j] = false;
            }

            for (var i = 2; i <= n; i++)
            {
                if (prime[i])
                    result.Add(i);
            }

            return result;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *