самый быстрый алгоритм для общего премьер-тестирования АКС. Статья в Википедии описывает его по длине и ссылкам на оригинальную статью.

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

алгоритм, который я обычно реализую (легко понять и код), выглядит следующим образом (в Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

это вариант классического . Он использует тот факт, что простое число (кроме 2 и 3) имеет форму 6k - 1 или 6k + 1 и смотрит только на делители эту форму.

иногда, если я действительно хочу скорость и диапазон ограничен, я реализую псевдо-простой тест на основе маленькая теорема Ферма. Если я действительно хочу больше скорости(т. е. вообще избегать алгоритма O(sqrt (N))), я предварительно вычисляю ложные срабатывания (см. Кармайкл числа) и выполните двоичный поиск. Это самый быстрый тест, который я когда-либо реализованный, единственный недостаток заключается в том, что диапазон ограничен.

лучший метод, на мой взгляд, это использовать то, что прошло раньше.

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

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

согласно Википедии,решето Эратосфена и сложности O(n * (log n) * (log log n)) требует O(n) - так что это довольно хорошее место, чтобы начать, если вы не тестируете для особенно больших чисел.

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}
this is just c++ implementation of above  AKS algorithm

https://en.wikipedia.org/wiki/AKS_primality_test

В Python 3:

def is_prime(a):
if a < 2:
    return False
elif a!=2 and a % 2 == 0:
    return False
else:
    return all (a % i for i in range(3, int(a**0.5)+1) )

объяснение: Простое число-число, делящееся только на себя и 1. Экс: 2,3,5,7...

1) Если a Если " а " меньше 2, то это не простое число.

2) elif a!=2 и % 2 == 0: Если " а " делится на 2, то это определенно не простое число. Но если a=2, мы не хотим оценивать это, поскольку это простое число. Отсюда и состояние!=2

3) вернуть все (a % i для i в диапазоне (3, int (a0.5)+1) ):** Сначала посмотрите, что делает команда all () в python. Начиная с 3 делим "а" до его квадратного корня (а**0,5). Если "a" делится, то вывод будет ложным. Почему квадратный корень? Допустим, a=16. Квадратный корень из 16 = 4. Нам не нужно оценивать до 15. Нам нужно только проверить до 4, чтобы сказать, что это не простое число.

дополнительные: Цикл для нахождения всех простых чисел в диапазоне.

for i in range(1,100):
if is_prime(i):
    print("{} is a prime number".format(i) )

Python 3:

def is_prime(a):
    return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))

слишком поздно для вечеринки, но надеюсь, что это поможет. Это актуально, если вы ищете большие простые числа:

для проверки больших нечетных чисел необходимо использовать тест ферма и / или тест Миллера-Рабина.

эти тесты используют модульное возведение в степень, что довольно дорого, для n биты возведения в степень вам нужно по крайней мере n большое умножение int и n большой инт подразделения. Это означает, что сложность модульного возведения в степень равна O (n3).

Так что прежде чем с помощью большой пушки, вам нужно сделать несколько пробных делений. Но не делайте это наивно, есть способ сделать их быстро. Сначала умножьте столько простых чисел вместе, сколько вписывается в слова, которые вы используете для больших целых чисел. Если вы используете 32-битные слова, умножьте 3*5*7*11*13*17*19*23*29=3234846615 и вычислите наибольший общий делитель с числом, которое вы проверяете, используя евклидов алгоритм. После первого шага число уменьшается ниже размера слова и продолжить алгоритм без выполнения завершите большие целочисленные деления. Если GCD != 1, это означает, что одно из простых чисел, которые вы умножили вместе, делит число, поэтому у вас есть доказательство, что оно не простое. Затем продолжить 31*37*41*43*47 = 95041567, и так далее.

после того, как вы протестировали несколько сотен (или тысяч) простых чисел таким образом, вы можете сделать 40 раундов теста Миллера-Рабина, чтобы подтвердить, что число простое, после 40 раундов вы можете быть уверены, что число простое, есть только 2^-80 шанс, что это не так (скорее всего, ваше оборудование неправильное срабатывание...).

у меня есть основная функция, которая работает до (2^61)-1 здесь:

from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))

объяснение:

The all() функция может быть переопределена следующим образом:

def all(variables):
    for element in variables:
        if not element: return False
    return True

The all() функция просто проходит через ряд bools / numbers и возвращает False если он видит 0 или False.

The sqrt() функция просто делает квадратный корень ряда.

для пример:

>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10

The num % x часть возвращает остаток числа / x.

наконец, range(2, int(sqrt(num))) означает, что он создаст список это начинается на 2 и заканчивается на int(sqrt(num)+1)

для получения дополнительной информации о диапазоне, взгляните на это сайт!

The num > 1 часть просто проверяет, если переменная num больше 1, потому что 1 и 0 не считаются простыми числа.

надеюсь, это помогло:)

В Python:

def is_prime(n):
    return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

более прямое преобразование из математического формализма в Python будет использовать все(n % p != 0... ), но это требует строгой оценки всех значений P. Элемент не любой версия может завершиться рано, если найдено истинное значение.

лучший алгоритм для простых чисел javascript

 function isPrime(num) {
      if (num <= 1) return false;
      else if (num <= 3) return true;
      else if (num % 2 == 0 || num % 3 == 0) return false;
      var i = 5;
      while (i * i <= num) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
        i += 6;
      }
      return true
    }

аналогичная идея алгоритма AKS, который был упомянут

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}

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

#!usr/bin/python3

def prime_check(*args):
    for arg in args:
        if arg > 1:     # prime numbers are greater than 1
            for i in range(2,arg):   # check for factors
                if(arg % i) == 0:
                    print(arg,"is not Prime")
                    print(i,"times",arg//i,"is",arg)
                    break
            else:
                print(arg,"is Prime")

            # if input number is less than
            # or equal to 1, it is not prime
        else:
            print(arg,"is not Prime")
    return

# Calling Now
prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
prime_check(#anynumber)         # Put any number while calling it will check.

myInp=int(input("Enter a number: "))
if myInp==1:
    print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
    for i in range(2,myInp//2+1):
        if myInp%i==0:
            print("The Number {} is not a prime no".format(myInp))
            print("Because",i,"times",myInp//i,"is",myInp)
            break
    else:
        print("The Number {} is a prime no".format(myInp))
else:
    print("Alas the no {} is a not a prime no".format(myInp))

можно использовать sympy.

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

С sympy документы. Первый шаг-поиск тривиальных факторов, которые, если они найдены, позволяют быстро вернуться. Далее, если сито достаточно большое, используйте разделительный поиск на сите. Для малых чисел выполняется набор детерминированных тестов Миллера-Рабина с базисами, которые, как известно, не имеют контрпримеров в своем диапазоне. Наконец, если число больше 2^64, выполняется сильный тест BPSW. Хотя это вероятный простой тест, и мы считаем, что контрпримеры существуют, нет известных контрпримеров

вы могли бы попробовать нечто подобное.

def main():
    try:
        user_in = int(input("Enter a number to determine whether the number is prime or not: "))
    except ValueError:
        print()
        print("You must enter a number!")
        print()
        return
    list_range = list(range(2,user_in+1))
    divisor_list = []
    for number in list_range:
        if user_in%number==0:
            divisor_list.append(number)
    if len(divisor_list) < 2:
        print(user_in, "is a prime number!")
        return
    else:
        print(user_in, "is not a prime number!")
        return
main()

маленькая память? Это не самый маленький, но шаг в правильном направлении.

class PrimeDictionary {
    BitArray bits;

    public PrimeDictionary(int n) {
        bits = new BitArray(n + 1);
        for (int i = 0; 2 * i + 3 <= n; i++) {
            bits.Set(i, CheckPrimality(2 * i + 3));
        }
    }

    public PrimeDictionary(IEnumerable<int> primes) {
        bits = new BitArray(primes.Max());
        foreach(var prime in primes.Where(p => p != 2)) {
            bits.Set((prime - 3) / 2, true);
        }
    }

    public bool IsPrime(int k) {
        if (k == 2) {
            return true;
        }
        if (k % 2 == 0) {
            return false;
        }
        return bits[(k - 3) / 2];
    }
}

конечно, вы должны указать определение CheckPrimality.

Я думаю, что одним из самых быстрых является мой метод, который я сделал.

void prime(long long int number) {
    // Establishing Variables
    long long int i = 5;
    int w = 2;
    const long long int lim = sqrt(number);

    // Gets 2 and 3 out of the way
    if (number == 1) { cout << number << " is hard to classify. \n";  return; }
    if (number == 2) { cout << number << " is Prime. \n";  return; }
    if (number == 3) { cout << number << " is Prime. \n";  return; }

    // Tests Odd Ball Factors
    if (number % 2 == 0) { cout << number << " is not Prime. \n";  return; }
    if (number % 3 == 0) { cout << number << " is not Prime. \n";  return; }

    while (i <= lim) {
        if (number % i == 0) { cout << number << " is not Prime. \n";  return; }
        // Tests Number
        i = i + w; // Increments number
        w = 6 - i; // We already tested 2 and 3
        // So this removes testing multepules of this
    }
    cout << number << " is Prime. \n"; return;
}

public static boolean isPrime(int number) {
 if(number < 2)
   return false;
 else if(number == 2 || number == 3)
        return true;
      else {
        for(int i=2;i<=number/2;i++)
           if(number%i == 0)
             return false;
           else if(i==number/2)
                return true;
      }
    return false;
}