Какой самый быстрый алгоритм поиска простых чисел?

Question

Какой самый быстрый алгоритм для определения простых чисел с помощью C ++? Я использовал алгоритм сита, но все еще хочу, чтобы он был быстрее!

Answer 1

Очень быстрое внедрение Сита Аткина - это primegen Дэна Бернштейна. Это сито более эффективно, чем Сито Эратосфена . Его страница содержит некоторую информацию о тестах.

Answer 2

Если это должно быть очень быстро, вы можете включить список простых чисел:
http://www.bigprimes.net/archive/prime/

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

Answer 3

Он, он, я знаю, что я некромант, отвечающий на старые вопросы, но я только что нашел этот вопрос, ища в сети способы реализации эффективных тестов простых чисел.

До сих пор я считаю, что самым быстрым алгоритмом тестирования простых чисел является Strong Probable Prime (SPRP). Я цитирую форумы Nvidia CUDA:

Одна из наиболее практичных нишевых проблем в теории чисел с идентификацией простых чисел. Учитывая N, как вы можете эффективно определить, является ли оно простым или нет? Это не просто тереетический проблема, это может быть реальная необходимость в коде, возможно, когда вам нужно динамически находить размер основной хеш-таблицы в определенных диапазонах. Если N что-то порядка 2 ^ 30, вы действительно хотите сделать 30000 деление тестов для поиска каких-либо факторов? Очевидно, нет.

Распространенным практическим решением этой проблемы является простой тест, называемый вероятный простой тест Эйлера и более мощное обобщение называется сильным вероятным праймом (SPRP). Это тест, который для целое число N может вероятностно классифицировать его как простое или нет, и повторные тесты могут увеличить вероятность правильности. Медленная часть самого теста в основном включает вычисление значения, аналогичного ^ (N-1) по модулю N. Любой, кто реализует шифрование с открытым ключом RSA варианты использовали этот алгоритм. Это полезно как для огромных целых чисел (например, 512 бит), а также обычные 32 или 64 битные.

Тест может быть изменен с вероятностного отклонения на окончательное доказательство первичности путем предварительного вычисления определенных входных данных теста параметры, которые, как известно, всегда успешны для диапазонов N. К сожалению, открытие этих «самых известных тестов» эффективно поиск огромного (фактически бесконечного) домена. В 1980 году первый список полезные тесты были созданы Карлом Померансом (известным тем, что для факторинга RSA-129 с его алгоритмом Quadratic Seive.) Позже Йешке значительно улучшили результаты в 1993 году. В 2004 году Чжан и Тан усовершенствовал теорию и границы области поиска. Грейтхаус и Ливингстон опубликовал самые современные результаты до сих пор на веб, на http://math.crg4.com/primes.html, лучшие результаты огромного поисковый домен.

Смотрите здесь для получения дополнительной информации: http://primes.utm.edu/prove/prove2_3.html и http://forums.nvidia.com/index.php?showtopic=70483

Если вам просто нужен способ генерирования очень больших простых чисел и вы не хотите генерировать все простые числа <целое число n, вы можете использовать тест Лукаса-Лемера для проверки простых чисел Мерсенна. Простое число Мерсенна имеет вид 2 ^ p -1. Я думаю, что тест Лукаса-Лемера - самый быстрый алгоритм, открытый для простых чисел Мерсенна. </p>

И если вы хотите использовать не только самый быстрый алгоритм, но и самое быстрое оборудование, попробуйте реализовать его с помощью Nvidia CUDA, написать ядро ​​для CUDA и запустить его на GPU.

Вы даже можете заработать немного денег, если обнаружите достаточно большие простые числа, EFF раздает призы от $ 50K до $ 250K: https://www.eff.org/awards/coop

Answer 4

Существует 100% математический тест, который проверяет, является ли число P простым или составным, и называется AKS Primality Test .

Концепция проста: для числа P, если все коэффициенты (x-1)^P - (x^P-1) делятся на P, тогда P - это простое число, в противном случае это составное число.

Например, учитывая P = 3, получим полином:

   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

И коэффициенты делятся на 3, поэтому число простое.

И пример, где P = 4, который НЕ является простым, даст:

   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

И здесь мы можем видеть, что коэффициенты 6 не делятся на 4, поэтому это НЕ простое число.

Полином (x-1)^P будет составлять P+1 слагаемых и может быть найден с помощью комбинации. Итак, этот тест будет выполняться во время выполнения O(n), поэтому я не знаю, насколько это будет полезно, поскольку вы можете просто выполнить итерацию по i от 0 до p и проверить оставшуюся часть.

Answer 5

Ваша задача решить, является ли конкретное число простым? Тогда вам нужен тест на простоту (легкий). Или вам нужно все простые числа до заданного числа? В этом случае простые сита хороши (легко, но требуют памяти). Или вам нужны главные факторы числа? Это потребует факторизации (сложно для больших чисел, если вы действительно хотите наиболее эффективные методы). Насколько большие цифры вы смотрите? 16 бит? 32 бита? больше?

Один умный и эффективный способ - это предварительно вычислить таблицы простых чисел и сохранить их в файле с использованием кодирования на битовом уровне. Файл считается одним длинным битовым вектором, тогда как бит n представляет целое число n. Если n простое, его бит устанавливается в единицу и в противном случае равен нулю. Поиск выполняется очень быстро (вы вычисляете смещение байта и битовую маску) и не требует загрузки файла в память.

Answer 6

Рабин-Миллер - это стандартный вероятностный тест на простоту. (вы запускаете его K раз, и входное число либо определенно составное, либо, вероятно, оно простое с вероятностью ошибки 4 ^-K . (несколько сотен итераций, и почти наверняка оно говорит вам правду)

Существует не вероятностный (детерминистский) вариант Рабина Миллера .

Большой Интернет Mersenne Prime Search (GIMPS), который установил мировой рекорд по величине проверенного простого (2 ^74,207,281 - 1 по состоянию на июнь 2017 года), использует несколько алгоритмы , но это простые числа в специальных формах. Однако приведенная выше страница GIMPS содержит некоторые общие детерминированные тесты первичности. Похоже, они указывают на то, что алгоритм является «самым быстрым», зависит от размера проверяемого числа. Если ваше число соответствует 64 битам, вам, вероятно, не следует использовать метод, предназначенный для работы с простыми числами из нескольких миллионов цифр.

Answer 7

Это зависит от вашего приложения. Есть несколько соображений:

• Вам нужна только информация о том, являются ли несколько чисел простыми, нужны ли все простые числа до определенного предела или вам (потенциально) нужны все простые числа?
• Насколько велики числа, с которыми вам приходится иметь дело?

Тесты Миллера-Рабина и аналоговые тесты выполняются только быстрее, чем сита для чисел более определенного размера (я думаю, где-то около нескольких миллионов). Ниже, используя пробное деление (если у вас есть только несколько чисел) или сито быстрее.

Answer 8

Я дам вам решить, будет ли он самым быстрым или нет.

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine("span = {0}", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine("number = {0}", i);
            }
        }
        Console.WriteLine("primes count = {0}",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

На моем ноутбуке Core 2 Duo с процессором 2,40 ГГц требуется примерно 82 секунды для поиска и печати простых чисел в диапазоне от 1 до 1 000 000. И он нашел 78,498 простых чисел.

Answer 9

Я не знаю ни одного предопределенного алгоритма, но я создал свой собственный, который очень быстрый. Он может обрабатывать 20 цифр менее чем за 1 секунду. Максимальная возможность этой программы составляет 18446744073709551615. Программа:

#include <iostream>
#include <cmath>
#include <stdlib.h>

using namespace std;

unsigned long long int num = 0;

bool prime(){
if(num % 2 == 0 || num == 1){
    return false;
}

unsigned long int square_root = sqrt(num);
for(unsigned long int i = 3;i <= square_root;i += 2){
    if(num % i == 0){
        return false;
    }
}

return true;
}

int main()
{
do{
    system("cls");
cout << "Enter number : ";
cin >> num;

if(prime()){
    cout<<"The number is a prime number"<<endl<<endl<<endl<<endl;
}else{
    cout<<"The number is not a prime number"<<endl<<endl<<endl<<endl;
}
system("pause");
}while(1);

return 0;
}

Answer 10

Я всегда использую этот метод для вычисления чисел простых чисел, следующих за алгоритмом сита.

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }