Полезен ли алгоритм определения НЕпростоты числа с 3 операций?
Надеюсь, что остаток берётся всё-таки от деления на 390, а не на 389 - иначе смысла в коде вообще не видно.
Итак, у нас есть 77 простых чисел, меньших 390. Четыре из них - 2,3,5,13 - не более, чем мусор, дающий лишние срабатывания алгоритма. В самом деле, если x%390==3, то x делится на 3, а значит, оно составное. Остальные 73 числа годятся.
Получается такая картина. Для простого x величина x%390 - некоторое число, взаимно простое с 390. Причём распределены эти остатки более-менее равномерно (на картинке они выглядят как красные столбики). Всего этих остатков 96.
Если x - простое число, то с вероятностью 73/96 остаток будет простым числом, и алгоритм честно скажет "скорее, простое". С вероятностью 23/96 - те самые 25% - остаток окажется составным, и алгоритм ошибётся.
Если x - составное, то вероятность того, что число объявят "скорее, простым" будет равна 77/390-1/ln(x) (первое слагаемое - вероятность того, что остаток оказался простым, а второе - доля простых чисел в окрестности x).
Можно легко избавиться от ошибки первого вида: для этого надо в массив charr положить не простые числа, а числа, взаимно простые с 390. Тогда если алгоритм скажет "составное", то так и есть.
Можно было вместо 390 взять N=30030=2*3*5*7*11*13. Если массив будет заполнен числами, взаимно простыми с N, то отсеиваться, как составные, будет 4 числа из 5, а ложных отсеиваний простых чисел не будет вообще.
Я попробую угадать алгоритм. Для числа 41041 это работает?