Существует ли простой алгоритм, который может определить, является ли X простым числом, и не сбить с толку простого смертного программиста?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытался проработать свой путь через Project Euler и заметил, что несколько проблем требуют, чтобы вы определили простое число как часть этого.
Я знаю, что могу просто разделить x на 2, 3, 4, 5, ..., квадратный корень из X, и если я получу квадратный корень, я могу (безопасно) предположить, что число простое.К сожалению, это решение кажется довольно неуклюжим.
Я изучал лучшие алгоритмы о том, как определить, является ли число простым, но быстро запутываюсь.
Существует ли простой алгоритм, который может определить, является ли X простым числом, и не сбить с толку простого смертного программиста?
Большое спасибо!
Решение
Первый алгоритм довольно хорош и часто используется в Project 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]
Я вижу, что тест первичности Ферма уже был предложен, но я работал через Структура и интерпретация компьютерных программ , и они также дают Миллера-Рабина тест (см. раздел 1.2.6, проблема 1.28) в качестве другой альтернативы. Я с успехом использую его для задач Эйлера.
Вот простая оптимизация вашего метода, которая не совсем решито из Эратосфена, но очень проста в реализации: сначала попробуйте разделить X на 2 и 3, а затем выполнить цикл по j = 1..sqrt (X) / 6, пытаясь разделить на 6 * j-1 и 6 * j + 1. При этом автоматически пропускаются все числа, кратные 2 или 3, и вы получаете довольно хорошее ускорение с постоянным коэффициентом.
Принимая во внимание следующие факты (из 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% 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 наличие списка простых чисел действительно необходимо. Я бы предложил вести список, который вы используете для каждой проблемы.
Я думаю, что вы ищете Сито Эратосфена .
Ваше право, самое простое - самое медленное. Вы можете оптимизировать это несколько.
Посмотрите на использование модуля вместо квадратных корней. Следите за своими простыми числами. вам нужно только разделить 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-код, который у меня есть, как только я его найду. Они похожи по стилю, просто меньше линий.
Вот простой тест на простоту в 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);
}
Я также работаю над проблемами проекта Euler и фактически только что закончил # 3 (по id), который представляет собой поиск наибольшего простого множителя составного числа (числа в?является 600851475143).
Я просмотрел всю информацию о простых числах (методы сита, уже упомянутые здесь) и о целочисленной факторизации в википедии и придумал алгоритм пробного деления методом перебора, который, как я решил, подойдет.
Итак, когда я решал задачи Эйлера для изучения ruby, я изучал кодирование своего алгоритма и наткнулся на библиотеку mathn, в которой есть Первоклассный и еще Целочисленный класс с prime_division способ.как же это круто.я смог получить правильный ответ на проблему с помощью этого фрагмента ruby:
require "mathn.rb"
puts 600851475143.prime_division.last.first
этот фрагмент выводит правильный ответ на консоль.конечно, в итоге я много читала и училась, прежде чем наткнулась на эту маленькую прелесть, я просто подумала, что поделюсь ею со всеми...
Мне нравится этот код 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
Конечно, если бы я вычислял партию чисел, я бы не пересчитывал кеш; Я бы сделал это один раз и сделал бы поиск в нем.
Не оптимизировано, но это очень простая функция.
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)
}
}
Алгоритм простого тестирования 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 есть еще один способ:
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()
