Sieve of Eratosthenes

Здравейте,

в моя трети пост искам да споделя едно просто решение за намиране на всички прости числа в даден интервал от цели числа. За целта ползвам един известен алгоритъм който се казва “Sieve of Eratosthenes” или преведено на български – “Сито на Ератостен”.

Идеята на алгоритъма е следната – имаме четири изходни числа – 2, 3, 5 и 7. Всички кратни на тези числа образуват множеството на сложните числа. Останалите, които не попадат в тази група (включително тези четири) са търсените от нас прости числа. Ефектът може да се види на картинката по-долу:

 

 

 

 

 

 

Решението на задачата следва принципа показан по-горе. Създава се масив от 10 000 000 елемента от булев тип с първоначална стойност false. След това с четири последователни цикъла  се намират всички кратни числа съответно на 2, 3, 5 и 7 и съответните елементи се променят на true. Накрая се проверяват кои числа са останали със стойност false – те са търсените от нас прости числа в зададения интервал.

using System;

class SieveOfErathostenes

{

    static void Main(string[] args)

    {

        int n = 10000000;

        bool[] numbers = new bool[n];

        numbers[0] = true;

        numbers[1] = true;

        numbers[2] = true;

        for (int i = 2; i < n; i += 2)

        {

            numbers[i] = true;

        }

        numbers[3] = true;

        for (int i = 3; i < n; i += 3)

        {

            numbers[i] = true;

        }

        numbers[5] = true;

        for (int i = 5; i < n; i += 5)

        {

            numbers[i] = true;

        }

        numbers[7] = true;

        for (int i = 7; i < n; i += 7)

        {

            numbers[i] = true;

        }

        Console.WriteLine("Prime numbers:");

        for (int i = 0; i < n; i++)

        {

            if (numbers[i] == true)

            {

                continue;

            }

            Console.Write("{0}, ", i);

        }

    }

}

 

Advertisement