Да, вы найдете в большинстве алгоритмов, которые вы можете обменять пространство на время. Другими словами, позволяя использовать больше памяти, скорость значительно увеличивается * a .
Я на самом деле не знаю алгоритм Миллера-Рабина, но, если он не будет проще, чем одно смещение влево / добавление и извлечение памяти, он будет сметен из воды предварительно рассчитанным сито.
Важная вещь здесь рассчитана заранее. Это хорошая идея с точки зрения производительности, чтобы предварительно рассчитать такие вещи, так как первый миллион простых чисел вряд ли изменится в ближайшем будущем: -)
Другими словами, создайте свое сито с чем-то вроде:
unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1};
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))
со всеми обычными предостережениями о том, чтобы не передавать такие вещи, как a++, в макросы. Это дает вам лучшее из обоих миров, ослепительно быстрый поиск в таблице для простых чисел, возвращаясь к методу вычисления для тех, кто находится за пределами диапазона.
Очевидно, что вы бы написали программу, используя один из других методов для генерации этой таблицы поиска - вам не нужно вводить все вручную.
Но, как и во всех вопросах оптимизации, измерьте, не угадайте!
* a Классическим случаем этого были некоторые триггерные функции, которые мне когда-то приходилось писать для встроенной системы. Это было конкурентное предложение по контракту, и у системы было немного больше памяти, чем у процессора.
Мы фактически выиграли контракт, так как наши контрольные показатели по функциям взорвали конкуренцию.
Почему? Потому что мы предварительно рассчитали значения в таблицу поиска, изначально рассчитанную на другом компьютере. Путем разумного использования редукции (понижение входных значений ниже 90 градусов) и свойств триггера (тот факт, что косинус - это просто фазовый сдвиг синуса, а остальные три квадранта связаны с первым), мы получили таблицу поиска до 180 записей (одна на полградуса).
Лучшие решения - это элегантные и хитрые: -)
Для чего стоит следующий код C сгенерирует такую таблицу для вас, все простые числа меньше четырех миллионов (из них 283 000).
#include <stdio.h>
static unsigned char primeTbl[4000000];
int main (void) {
int i, j;
for (i = 0; i < sizeof(primeTbl); i++)
primeTbl[i] = 1;
primeTbl[0] = 0;
primeTbl[1] = 0;
for (i = 2; i < sizeof(primeTbl); i++)
if (primeTbl[i])
for (j = i + i; j < sizeof(primeTbl); j += i)
primeTbl[j] = 0;
printf ("static unsigned char primeTbl[] = {");
for (i = 0; i < sizeof(primeTbl); i++) {
if ((i % 50) == 0) {
printf ("\n ");
}
printf ("%d,", primeTbl[i]);
}
printf ("\n};\n");
printf ("#define isPrime(x) "
"((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n");
return 0;
}
Если вы можете увеличить таблицу primeTbl до шестнадцати миллионов записей (16M), то обнаружите, что этого достаточно, чтобы число простых чисел превысило миллион (первые 1 031 130 простых чисел).
Теперь есть способы сделать так, чтобы они занимали меньше места, например, сохраняя нечетные числа и настраивая макрос, чтобы позаботиться об этом, или используя битовую маску вместо беззнаковых символов. Я сам предпочитаю простоту алгоритмов, если память доступна.