Здравствуйте Курилка, Вы писали:

К>По-моему кроме как перебором это никак не решается и вероятности тут не помогут...

Вероятности помогут вот в каком смысле:
Предположим, существует тест, который определяет, что с вероятностью < 1/2 число является составным. Если каждый из k таких независимых тестов скажет, что число составное с вероятностью < 1/2, то значит мы можем утверждать, что число составное с вероятностью < (1/2)^k. При достаточно больших k (на практике хватит ~50) мы можем утверждать в этом случае, что число простое (вероятность, что мы назовем простое число составным, как видно, очень мала).

А вот пара таких тестов (проверяем на простоту число p):

I) Тест Леманна

1) Выбираем случайно число a, меньшее p
2) Вычисляем r=a^((p-1)/2) mod p
3) Если r!=1 && r!=-1 (mod p), то p не является простым.
4) Если r==1 || r==-1 (mod p), то вероятность того, что p не является простым <= 1/2

Повторяем такие проверки k раз. Если результат равен 1 или -1, но не всегда равен 1, то p наверняка простое число (с вероятностью ошибки 1/(2^k)).

II) Очень распространенный тест Рабина-Миллера

Вычислим b — число делений p-1 на 2 (т.е. 2^b — это наибольшая степень числа 2, на которое делится p-1). Затем вычислим m, такое что p=1+(2^b)*m (т.е. m — остаток от деления p-1 на 2^b).

1) Выберем случайное число a, меньшее p.
2) j=0; z=(a*m) mod p
3) Если z==1 или если z==p-1, то p проходит проверку и может быть простым числом.
4) Если j>0 и z==1, то p не является простым числом.
5) j=j+1. Если j<b и z<p-1, устанавливаем z=(z*z) mod p и возвращаемся на шаг 4). Еслм z==p-1, то p проходит проверку и может быть простым числом.
6) Если j==b и z!=p-1, то, p не является простым числом.

В этом тесте вероятность прохождения проверки на простоту составным числом убывает быстрее, чем в предыдущем. Вероятность того, что мы назовем составное число простым после k таких тестов не больше (1/4)^k.