Существует ли простой алгоритм, который может определить, является ли X главным, и не смущают простого смертного программиста?

иначе в 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()  

Главный алгоритм тестирования AKS:

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;   

Мне нравится этот код 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

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

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

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

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

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

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

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

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

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

Вот мой 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, который я имею, а также скоро поскольку я нахожу его. Они подобны в стиле, просто меньше строк.

Вот простой тест простоты чисел в D (Цифровой Марс):

/** 
 * 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);
}

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

я думаю, что Вы ищете, Решето Эратосфена .

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

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

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

тест 2, 3, и кратные числа 6 + или - 1 (все начала кроме 2 или 3 являются кратными числами 6 +/-1, таким образом, Вы по существу просто пропускаете все четные числа и все кратные числа 3

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

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

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

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

Я рекомендовал бы тест простоты чисел Fermat . Это - вероятностный тест, но это корректно удивительно часто. И это невероятно быстро по сравнению с решетом.

Учет следующих фактов (от 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)
}

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

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

Я вижу, что тест простоты чисел Fermat был уже предложен, но я работал до Структура и Интерпретация Компьютерных программ , и они также дают тест Miller-Rabin (см. Раздел 1.2.6, проблема 1.28) как другая альтернатива. Я использовал его с успехом для Euler проблем.

Для генерации всех простых чисел меньше, чем предел , Решето Эратосфена (страница содержит варианты на 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]