Какой самый быстрый алгоритм для идентификации простых чисел из массива случайных чисел?

Question

У меня есть массив случайных чисел, и я должен вернуть простые числа из этого массива. Я знаком с решением root(n) (n - это конкретное число, а не размер массива). Я не могу применить сито Эратосфена, так как оно работает с числами в определенном диапазоне, но здесь числа совершенно случайны.

Пожалуйста, поправьте меня, если я что-то упустил. Заранее спасибо!

Answer 1

Вы ищете тест на первичность. Вы должны быть в состоянии искать и находить много возможностей. Вот ответ, который я написал несколько лет назад и который, вероятно, намного больше, чем вы хотите:

Самый быстрый способ узнать, является ли данное число простым

Большинство деталей касаются чисел больше 64-битных, где есть много возможных отклонений и вариантов. Для 64-битных входов простым и разумным ответом является использование небольшого пробного деления, за которым следует специально разработанный набор тестов Миллера-Рабина, которые дают детерминированные результаты (при этом не используется ни случайность, ни вероятность ошибки при правильном применении). Если вы хотите немного оптимизировать, то есть хэшированные наборы и BPSW для рассмотрения.

Приложение: Есть случаи, которые могут быть выполнены быстрее, если количество входов намного больше, чем максимальный размер входа или количество уникальных входов, или если есть некоторое распределение, такое как ожидание множества повторных входов. Тогда такие решения, как кэширование или создание набора битов для быстрого поиска, могут быть быстрее. Знание входного набора очень помогает.

Answer 2

Если пробел важен, и вы знакомы с C++, вы можете использовать набор битов вместо bool, что будет улучшением в 8 раз, потому что bool использует 8 битов для элемента, тогда как набор битов использует только один бит для хранения значения 1 или 0;

const int SIZE = 1000000;
const int LIMIT = sqrt(SIZE)+1;

bitset<SIZE> prime;

void sieve() {
    prime.flip();
    prime[1]=0;
    for(int i=2;i<=LIMIT;i++) {
        if (prime[i])
            for(int j=2*i;j<SIZE;j+=i)
                prime[j]=0;
    }
}

bool isPrime(int n) {
    return prime[n];
}

Answer 3

Каждое простое число смежно с 6n (где n>=1) .

Убедитесь, что число смежно с числом, кратным 6 .

Если число смежно, примените алгоритм проверки простоты к этому числу. Обоснование для метода 6n: https://www.youtube.com/watch?v=ZMkIiFs35HQ