Эратосфен селтәре

Эратосфен селтәре (иләге) — натураль һандар рәтенең башынан алып билгеле бер натураль һанға тиклем арала, тик ябай һандар булған йәҙүәлдең (таблицаның) төҙөү методы.

Алгоритмы

Эратосфен алгоритмы

Мәҫәлән, 120-гә тиклем булған һандар араһындағы ябай һандар йәҙүәлен төҙөү өсөн, 2-нән алып 120-гә тиклем барлыҡ натураль һандарҙы яҙалар. Шунан 2-нән һуң һәр икенсе урында килгән һанды һыҙып ырғыталар. Шулай итеп 2-гә бүленә торған барлыҡ һандар төшөп ҡала. Шунан, 2-нән һуң һыҙылмайынса ҡалған беренсе һандың 3-кә тигеҙ булғанын күрәбеҙ. 3-тән һуң һәр саҡ өсөнсө урында йәғни 3-кә бүленә торған барлыҡ һандарҙы һыҙалар. Был саҡта беренсе һыҙылмайынса ҡалған ябай һан 5-кә тигеҙ булсаҡ. Шулай дауам иткәндә бары тик ябай һандар ғына һыҙылмайынса ҡаласаҡ.

Әҙәбиәт

• Гальперин Г. «Просто о простых числах» // Квант (журнал). — № 4.
• Под. ред. Невская И.И. Неопубликованные материалы Л.Эйлера по теории чисел. — "Наука", 1997.
• Проф. Д.Ф.Егоров. Элементы теории чисел. — Государственное издательство Москва, 1923.
• Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

Һылтанмалар

• Решето Эратосфена от М. Гарднера
• Алгоритм составления таблицы простых чисел от заданного до другого числа
• Реализация алгоритма поиска простых чисел на Java
• Доказательство сложности алгоритма
• Еще раз о поиске простых чисел