Каков наилучший алгоритм проверки, является ли число простым?

Question

Просто пример того, что я ищу: я мог бы представить каждое нечетное число с битом, например, для данного диапазона чисел (1, 10], начинается с 3:

1110

Следующий словарь можно сжать более правильно? Я мог бы определить кратные пять с некоторой работой, но числа, заканчивающиеся на 1, 3, 7 или 9, должны быть там в массиве битов. Надеюсь, это прояснит, чего я хочу.

Я ищу лучший алгоритм, чтобы проверить, простое ли число, то есть булева функция:

bool isprime(number);

Я хотел бы знать лучший алгоритм для реализации этой функциональности. Естественно, была бы структура данных, которую я мог бы запросить. I определяет наилучший алгоритм , который представляет собой алгоритм, который создает структуру данных с самым низким потреблением памяти для диапазона (1, N], где N - константа.

Answer 1

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

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

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

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

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

Answer 2

import math
import time


def check_prime(n):

    if n == 1:
        return False

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    from_i = 3
    to_i = math.sqrt(n) + 1

    for i in range(from_i, int(to_i), 2):
        if n % i == 0:
            return False
    return True

Answer 3

лучший алгоритм для простого числа 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
    }

Answer 4

В Python:

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

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

Answer 5

У меня есть простая функция, которая работает до (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)))

Пояснение:

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

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

Функция all() просто просматривает серию bools / numbers и возвращает False, если видит 0 или False.

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

Например:

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

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

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

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

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

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

Answer 6

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

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.

Answer 7

Вот мой взгляд на ответ:

def isprime(num):
    return num <= 3 or (num + 1) % 6 == 0 or (num - 1) % 6 == 0

Функция вернет True, если какое-либо из свойств ниже - True. Эти свойства математически определяют, что такое простое число.

1. Число меньше или равно 3
2. Число + 1 делится на 6
3. Число - 1 делится на 6

Answer 8

Первое правило простого числа: если разделить на 2, это будет целое число или целое число Нет, это не простое число.

Самый быстрый способ узнать, используя любой компьютерный язык, - это сопоставление типов с использованием строк, а не математики. Сопоставьте ТОЧКУ в струнном Float.

• Разделите это на 2 ,,, n = n / 2
• Преобразовать это в строку ,,, n = string (n)
• если "." гостиница: { printf «Да, я премьер!»
  }

Answer 9

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

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;
}

Answer 10

С помощью потоков и лямбд Java-8 это может быть реализовано следующим образом:

public static boolean isPrime(int candidate){
        int candidateRoot = (int) Math.sqrt( (double) candidate);
        return IntStream.range(2,candidateRoot)
                .boxed().noneMatch(x -> candidate % x == 0);
    }

Производительность должна быть близка к O (sqrt (N)) . Может быть, кто-то найдет это полезным.