Виталий Пухов: Но если воспользоваться детерминированным тестом Миллера, то достаточно будет прогнать тест Миллера-Рабина для всех стартовых значений от 2 до 107000 (=2*ln(10^100)^2), т.е. можно уложиться в 20 минут. Для 1000-значного числа потребуется уже 200000 минут, или 5 месяцев. Но более быстрый алгоритм вы вряд ли найдёте.
Дѣаволъ: На самом деле, это не важно. Для таких чисел потребуется примерно 2^80 операций, т.е. несколько миллионов лет при расчёте на одном ядре (сколько именно - зависит от быстродействия компьютера и качества реализации алгоритма). За разумное время - от дня до года - можно попробовать доказать простоту 100-значного числа. А для него и памяти нужно гораздо меньше.
Хороший алгоритм. Но для 1000-значного числа (скажем, 4096 бит), даже если мы найдём простые q,r, такие, что r=2*q+1, q>2^24 (судя по алгоритму из английской версии, этого достаточно), то нам понадобится примерно 64 или 80 ГБ памяти - только для возведения многочлена в степень.
Виталий Пухов: Это всё равно, что сказать "число произвольное". Так что придётся применять общие алгоритмы.
Учтите ещё, что вероятность того, что число с миллионом знаков простое - примерно 1/2300000. Так что чисел для поиска такого числа придётся перебрать много.
Если хотите искать большие простые числа - ищите их в виде 2*p*q+1, где p и q - тоже простые. Можно добавить ещё несколько простых множителей, но не очень много. Простоту таких чисел проверить (гарантированно) гораздо проще: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D...
Виталий Пухов: Почему это? Получается число N=B*10^(1000+L)+C, где L - число знаков в C. Так что остаток от деления N на B - как раз C. А остаток от деления на 1000 - три последних цифры C.
А можно перебирать числа подряд от 10^1000, и считать для каждого остаток от деления на B (последовательным вычитанием). Когда получится C - закончить.
С другой стороны, вероятность того, что для каких-то двух пар эти числа совпадут, равна 2^(-64). И даже для миллиарда пар шансы получить одинаковый код хотя бы у двух будут меньше 1%. С практической точки зрения, этим можно пренебречь. Так что a+b*3141592653 будет вполне подходящим вариантом. Посчитать его с помощью битовых операций трудно, но можно.
Если в программе исключения используются для отработки штатных ситуаций, то практически невозможной становится отладка в режиме "остановиться, когда будет выброшено исключение". Особенно, если это какой-нибудь null reference.
Сергей: А вы не думайте в терминах "начинать новый отсчёт". Подумайте об индивидуальном элементе - что бы вы хотели увидеть в строке вывода на этом месте? И как его получить, зная $i?
Возьмите короткий массив (7 элементов). Напишите вывод за 3-4 дня. И попробуйте увидеть закономерность и найти формулу.
