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

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

Здесь функция С++, используемая для относительно малого 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)
}

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

Ответ 6

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

Ответ 7

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

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

test 2 и нечетные числа.

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

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

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

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

Ответ 10

Вот простой тест примитивности в 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);
}

Ответ 11

Я работаю над проблемами Project Euler, а на самом деле только что закончил # 3 (по id), который является поиском наивысшего основного коэффициента составного числа (число в 600001475143).

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

Так как я делаю проблемы с Эйлером, чтобы изучить Ruby, я искал кодировку своего алгоритма и наткнулся на библиотеку mathn, у которой Prime class и класс Integer с методом prime_division. как это круто. я смог получить правильный ответ на проблему с этим фрагментом ruby:

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

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

Ответ 12

Алгоритм простого тестирования 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;   

Ответ 13

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

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

Ответ 14

Удивлен, что никто не представил версию PHP, поэтому здесь мое представление:

function sieve_of_erathosthenes($max) {

    // populate array
    for ($i = 2; $i <= $max; $i++) {
        $array[] = $i;
    }

    // sieve of eratosthenes algo
    for ($i = 0, $j = count($array); $i < $j; $i++) {
        $prime[] = $p = array_shift($array);

        foreach ($array as $k => $v) {
            if ($v % $p == 0){
                unset($array[$k]);
                $j--;
            }
        }       
    }

    return $prime;

}

Ответ 15

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

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

Ответ 16

другой способ в 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()