Как определить многозначное простое число?

Question

От 1 000 000 и боле. Есть ли другие методы кроме трудоемкого "решета Эратосфена"? Меня интересует мнение только математиков! Если число заканчивается на 0 и 5 это уже не простое число. Это понятно! Возможно проводились какие-то исследования?

Answer 1

Тьма исследований проводилась. Простые числа очень важны для криптографии. И, конечно, разработано много сложных методов определения простоты числа.
Например, ru. wikipedia. org/wiki/Тест_Адлемана_—_Померанса_—_Румели
А простоту чисел порядка миллиона с помощью компьютеров даже старинными методами определять пустяк, эти числа считаются очень маленькими. Даже простейшими старинными методами для такого числа компьютер на определение его простоты потратит несколько миллионных долей секунды.
А наибольше найденное сейчас простое число содержит 21 миллион цифр. Для этого, конечно, потребовались современные методы и суперкомпьютер.

Answer 2

Мнение математиков тебе не нужно, нужен один запрос в гугл.
Если бы тебе это действительно было интересно, ты бы знал, что поиск простых чисел — очень трудоемкая задача. Именно поэтому простые числа широко используют в криптографии (RSA, как самый известный) .
Алгоритмов нахождения простых чисел куда больше одного, даже в статье в Википедии про решето Эратосфена прямо указаны еще два. А если копнуть глубже.
Но чукча ж не читатель.