Сайт о программировании, математике и моделировании
Записи с метками решето Эрастофена
Методы проверки на простоту
1 Декабрь
Все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют это определить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной. Читать дальше >
Решето Эрастофена
1 Декабрь
Если известно, что N мало, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если N меньше миллиона, то нужно включить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить значение d168 = 1000 как заключительного члена для случая, когда число N окажется простым, большим 9972). Такую таблицу можно получить при помощи короткой вспомогательной программы. Читать дальше >
