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

Question

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

1. Я знаю, что могу просто разделить x на 2, 3, 4, 5, ..., квадратный корень из X и, если я доберусь до квадратного корня, я могу (безопасно) предположить, что число простое , К сожалению, это решение кажется довольно клунким.

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

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

Большое спасибо!

Answer 1

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

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

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

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

Answer 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]

Answer 3

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

Answer 4

Имея в виду следующие факты (из 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)
}

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

Answer 5

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

Answer 6

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

Answer 7

Для относительно небольших чисел 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 для тех, которые находятся вне диапазона сита.

Answer 8

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

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

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

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

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

Answer 9

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

Answer 10

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

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

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

---

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