Новые процессоры возникают довольно часто. Иногда даже с новыми системами команд. И через какое-то время для них появляется си-компилятор. Когда сделают новый процессор, то, во-первых, многие из тех, кто сейчас программирует на си, легко освоят для него и ассемблер, и машинные коды, а во-вторых, компилятор с языка, очень похожего на си, появится быстро (поскольку этот подход уже доказал свою эффективность). Так что знания никуда не пропадут.
Виталий Пухов: Разложение является тривиальной задачей для чисел, которые строятся, как произведение известных простых чисел. Там разложение известно сразу.
Для вашей задачи теста Миллера-Рабина более, чем достаточно. Если 10 случайных проверок дадут положительный результат, то вероятность того, что число составное - меньше одной миллионной. Так что доля простых чисел, которая получится по результатам проверки, будет очень близка к истине (ошибка будет соответствовать статистической погрешности).
Виталий Пухов: Но если воспользоваться детерминированным тестом Миллера, то достаточно будет прогнать тест Миллера-Рабина для всех стартовых значений от 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 будет вполне подходящим вариантом. Посчитать его с помощью битовых операций трудно, но можно.
