Простые числа. Решето Эратосфена

Это ста­тья по­свя­ще­на про­стым чис­лам и эф­фек­тив­ным спо­со­бам их вы­чис­ле­ния. Сра­зу ска­жу, что те ал­го­рит­мы, ко­то­рые тут при­ве­де­ны, яв­ля­ют­ся весь­ма и весь­ма нетри­ви­аль­ны­ми и са­мо­му мне не да­ва­лись до­воль­но дол­го, но в ито­ге я их всё-таки при­ду­мал, на­пи­сал и спе­шу по­де­лить­ся со все­ми вами. Ис­ход­ные тек­сты в ста­тье бу­дут при­ве­де­ны на язы­ках C# и Haskell.

Про­стое чис­ло – это на­ту­раль­ное чис­ло боль­ше еди­ни­цы, ко­то­рое име­ет ров­но два де­ли­те­ля: еди­ни­цу и само это чис­ло.

Ре­ше­то Эра­то­сфе­на – древ­ний, но при этом весь­ма эф­фек­тив­ный и до сих пор ши­ро­ко ис­поль­зу­е­мый ал­го­ритм по­ис­ка всех про­стых чи­сел не пре­вос­хо­дя­щих неко­то­ро­го N.

За­пи­шем под­ряд все чис­ла от 2 до N. Даль­ше вы­черк­нем из это­го спис­ка все чис­ла крат­ные 2, ис­клю­чая саму двой­ку, по­том вы­черк­нем все чис­ла крат­ные 3, ис­клю­чая само чис­ло 3, чис­ло 4 уже вы­черк­ну­то, вы­чер­ки­ва­ем чис­ла крат­ные 5 и т.д. Про­дол­жа­ем этот про­цесс, пока квад­рат оче­ред­но­го чис­ла не пре­вы­сит N.

Са­мая про­стая про­грамм­ная ре­а­ли­за­ция это­го ал­го­рит­ма вы­гля­дит сле­ду­ю­щим об­ра­зом:

(далее...)