Есть ли простой алгоритм, который может определить, является ли X простым?

Первый алгоритм довольно хорош и часто используется в Project Euler. Если вы знаете максимальное количество, которое вы хотите, вы также можете исследовать сито Эратосфена.

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

С помощью этих двух алгоритмов (разделения и сита) вы сможете решить проблемы.

Редактировать: фиксированное имя, как указано в комментариях

Для Project Euler очень важно иметь список простых чисел. Я бы посоветовал вести список, который вы используете для каждой проблемы.

Я думаю, что вы ищете Сито Эратосфена.

Алгоритм тестирования AKS Prime:

Input: Integer n > 1  


if (n is has the form ab with b > 1) then output COMPOSITE  

r := 2  
while (r < n) {  
    if (gcd(n,r) is not 1) then output COMPOSITE  
    if (r is prime greater than 2) then {  
        let q be the largest factor of r-1  
        if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break  
    }  
    r := r+1  
}  

for a = 1 to 2sqrt(r)log n {  
    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE  
}  

output PRIME;   

Я бы рекомендовал Тест на простоту Ферма. Это вероятностный тест, но на удивление часто он оказывается верным. И это невероятно быстро по сравнению с ситом.

Вот простая оптимизация вашего метода, которая не совсем решетка Эратосфена, но очень проста в реализации: сначала попробуйте разделить X на 2 и 3, затем переберите j = 1..sqrt (X) / 6, пытаясь разделить на 6 * j-1 и 6 * j + 1. Это автоматически пропускает все числа, делящиеся на 2 или 3, что дает вам довольно приятное постоянное ускорение.

Ваше правое простое - самое медленное. Вы можете его несколько оптимизировать.

Изучите использование модуля вместо квадратных корней. Следите за своими простыми числами. вам нужно только разделить 7 на 2, 3 и 5, поскольку 6 кратно 2 и 3, а 4 кратно 2.

Rslite упомянул эрантенос сито. Это довольно просто. Он у меня дома на нескольких языках. Добавьте комментарий, если хотите, чтобы я опубликовал этот код позже.

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

// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>

int main(void) {
        // using unsigned short.
        // maximum value is around 65000
        const unsigned short max = 50000;
        unsigned short x[max];
        for(unsigned short i = 0; i < max; i++)
                x[i] = i + 2;

        for(unsigned short outer = 0; outer < max; outer++) {
                if ( x[outer] == 0)
                        continue;
                unsigned short item = x[outer];
                for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
                        unsigned int searchvalue = item * multiplier;
                        unsigned int maxValue = max + 1;
                        for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
                                if (x[maxIndex] != 0) {
                                        maxValue = x[maxIndex];
                                        break;
                                }
                        }
                        for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
                                if ( searchvalue > maxValue )
                                        break;
                                if ( x[searchindex] == searchvalue ) {
                                        x[searchindex] = 0;
                                        break;
                                }
                        }
                }
        }
        for(unsigned short printindex = 0; printindex < max; printindex++) {
                if (x[printindex] != 0)
                        std::cout << x[printindex] << "\t";
        }
        return 0;
}

Я подброшу имеющийся у меня код Perl и python, как только найду его. Они похожи по стилю, только меньше линий.

Я вижу, что тест на простоту Ферма уже предлагался, но я работал с Структура и интерпретация компьютерных программ, и они также дают Тест Миллера-Рабина (см. Раздел 1.2.6, проблема 1.28) в качестве другой альтернативы. Я успешно использовал его для задач Эйлера.

Вот простой тест на простоту в D (Digital Mars):

/** 
 * to compile:
 * $ dmd -run prime_trial.d
 * to optimize:
 * $ dmd -O -inline -release prime_trial.d 
 */
module prime_trial;

import std.conv : to;  
import std.stdio : w = writeln;

/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 
bool 
isprime(Integer)(in Integer number) 
{
  /* manually test 1, 2, 3 and multiples of 2 and 3 */
  if (number == 2 || number == 3)
    return true;
  else if (number < 2 || number % 2 == 0 || number % 3 == 0)
    return false;

  /* we can now avoid to consider multiples 
   * of 2 and 3. This can be done really simply 
   * by starting at 5 and incrementing by 2 and 4 
   * alternatively, that is: 
   *    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...    
   * we don't need to go higher than the square root of the number */
  for (Integer divisor = 5, increment = 2; divisor*divisor <= number; 
       divisor += increment, increment = 6 - increment) 
    if (number % divisor == 0)
      return false;

  return true;  // if we get here, the number is prime
}

/// print all prime numbers less then a given limit
void main(char[][] args) 
{
  const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
  for (uint i = 0; i < limit; ++i) 
    if (isprime(i))
      w(i);
}

Сгенерировать все простые числа меньше предела Сито Эратосфена (страница содержит варианты на 20 языках программирования) - это самое старое и простое решение.

В Python:

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

Пример:

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

Для достаточно малых чисел x% n до sqrt (x) ужасно быстро и легко кодируется.

Простые улучшения:

тест 2 и только нечетные числа.

тест 2, 3 и кратные 6 + или - 1 (все простые числа, кроме 2 или 3, кратны 6 +/- 1, поэтому вы по сути просто пропускаете все четные числа и все числа, кратные 3

проверять только простые числа (требуется вычислить или сохранить все простые числа до sqrt (x))

Вы можете использовать метод sieve для быстрого создания списка всех простых чисел до некоторого произвольного предела, но он обычно требует больших затрат памяти. Вы можете использовать прием, кратный 6, чтобы уменьшить использование памяти до 1/3 бита на число.

Я написал простой простой класс (C#), который использует два битовых поля для кратных 6 + 1 и кратных 6-1, затем выполняет простой поиск ... и если число, которое я тестирую, находится за пределами сита, затем он возвращается к тестированию на 2, 3 и кратные 6 +/- 1. Я обнаружил, что создание большого сита на самом деле занимает больше времени, чем вычисление простых чисел на лету для большинства задач Эйлера, которые я решил до сих пор. Принцип KISS снова поражает!

Я написал простой класс, который использует сито для предварительного вычисления меньших простых чисел, а затем полагается на тестирование на 2, 3 и кратные шести +/- 1 для тех, которые находятся за пределами диапазона сита.

Я также работаю над проблемами Project Euler и фактически только что закончил № 3 (по идентификатору), который является поиском наивысшего простого множителя составного числа (число в? ​​600851475143).

Я просмотрел всю информацию о простых числах (методы сита, уже упомянутые здесь), а также о целочисленной факторизации в Википедии и придумал алгоритм деления методом грубой силы, который, как я решил, подойдет.

Итак, когда я решаю задачи Эйлера для изучения рубина, я искал кодировку своего алгоритма и наткнулся на библиотеку mathn, в которой есть методы Прайм класс и Целочисленный класс с prime_division. как это круто. я смог получить правильный ответ на проблему с помощью этого фрагмента рубина:

require "mathn.rb"
puts 600851475143.prime_division.last.first

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

Принимая во внимание следующие факты (из MathsChallenge.net):

• Все простые числа, кроме 2, нечетные.
• Все простые числа больше 3 можно записать в виде 6k - 1 или 6k + 1.
• Вам не нужно проверять квадратный корень из n

Вот функция C++, которую я использую для относительно небольших n:

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

Вероятно, вы могли бы подумать о дополнительных собственных оптимизациях.

Мне нравится этот код на Python.

def primes(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] ==  i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    return [j for j in xrange(2, limit) if x[j] == 1]

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

def factors(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] == i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    result = []
    y = limit-1
    while x[y] != 1 :
        divisor = x[y]
        result.append(divisor)
        y /= divisor
    result.append(y)
    return result

Конечно, если бы я факторизовал пакет чисел, я бы не пересчитывал кэш; Я бы сделал это один раз и сделал бы поиск в нем.

другой способ в Python:

import math

def main():
    count = 1
    while True:
        isprime = True

        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break

        if isprime:
            print count


        count += 2


if __name__ == '__main__':
    main()  

Не оптимизирован, но это очень простая функция.

    function isprime(number){

    if (number == 1)
        return false;

    var times = 0;

    for (var i = 1; i <= number; i++){
        if (number % i == 0){
            times ++;
        }
    }
        if (times > 2){
            return false;
        }

    return true;
    }

Возможно, эта реализация на Java может быть полезной:

public class SieveOfEratosthenes {

    /**
     * Calling this method with argument 7 will return: true true false false true false true false
     * which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
     * 5 is prime, 6 is NOT prime, 7 is prime.
     * Caller may either revert the array for easier reading, count the number of primes or extract the prime values
     * by looping.
     * @param upTo Find prime numbers up to this value. Must be a positive integer.
     * @return a boolean array where index represents the integer value and value at index returns
     * if the number is NOT prime or not.
     */
    public static boolean[] isIndexNotPrime(int upTo) {
        if (upTo < 2) {
            return new boolean[0];
        }

        // 0-index array, upper limit must be upTo + 1
        final boolean[] isIndexNotPrime = new boolean[upTo + 1];

        isIndexNotPrime[0] = true; // 0 is not a prime number.
        isIndexNotPrime[1] = true; // 1 is not a prime number.

        // Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
        // Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
        // Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
        // Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
        // Repeat process until i * i > isIndexNotPrime.len.
        // Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
        // primes above 121..
        for (int i = 2; i < isIndexNotPrime.length; i++) {
            if (i * i >= isIndexNotPrime.length) {
                break;
            }
            if (isIndexNotPrime[i]) {
                continue;
            }
            int multiplier = i;
            while (i * multiplier < isIndexNotPrime.length) {
                isIndexNotPrime[i * multiplier] = true;
                multiplier++;
            }
        }

        return isIndexNotPrime;
    }

    public static void main(String[] args) {
        final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
        assert !indexNotPrime[2]; // Not (not prime)
        assert !indexNotPrime[3]; // Not (not prime)
        assert indexNotPrime[4]; // (not prime)
        assert !indexNotPrime[5]; // Not (not prime)
        assert indexNotPrime[6]; // (not prime)
        assert !indexNotPrime[7]; // Not (not prime)
    }
}