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

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

Если важен пробел и вы знакомы с 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];
}