Записи с метками решето Эрастофена

1

Методы проверки на простоту

1 Декабрь

Опубликовал root в Алгоритмы

1 комментарий

Все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют это определить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной. Читать дальше >

, , , , ,

Решето Эрастофена

1 Декабрь

Опубликовал root в Алгоритмы

Комментариев: 3

Если известно, что N мало, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если N меньше миллиона, то нужно вклю­чить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить зна­чение d168 = 1000 как заключительного члена для случая, когда число N окажется простым, большим 9972). Такую таблицу можно получить при помощи короткой вспомогательной программы. Читать дальше >

, , ,