Existe um algoritmo simples que pode determinar se X é Prime e não confundir um mero programador mortal?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho tentado trabalhar meu caminho através do Project Euler e notei um punhado de problemas, pede que você determine um número primo como parte dele.
Eu sei que posso apenas dividir x por 2, 3, 4, 5, ..., raiz quadrada de x e se eu chegar à raiz quadrada, posso (com segurança) assumir que o número é primitivo. Infelizmente, essa solução parece bastante klunky.
Eu analisei melhores algoritmos sobre como determinar se um número é primo, mas fique confuso rapidamente.
Existe um algoritmo simples que pode determinar se X é Prime e não confundir um mero programador mortal?
Muito obrigado!
Solução
O primeiro algoritmo é muito bom e usado muito no Projeto Euler. Se você conhece o número máximo que deseja, também pode pesquisar a peneira de Eratostenes.
Se você manter a lista de primos, também poderá refinar o primeiro algo a se dividir apenas com os primos até a raiz quadrada do número.
Com esses dois algoritmas (dividindo e a peneira), você poderá resolver os problemas.
Editar: Nome corrigido, conforme observado nos comentários
Outras dicas
Para gerar todos os números primos menores que um limite Peneira de eratóstenes (A página contém variantes em 20 linguagens de programação) é a solução mais antiga e mais simples.
Em 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
Exemplo:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Vejo que o teste de primalidade de Fermat já foi sugerido, mas eu tenho trabalhado Estrutura e interpretação de programas de computador, e eles também dão o Teste de Miller-Rabin (Consulte a Seção 1.2.6, Problema 1.28) Como outra alternativa. Eu o uso com sucesso para os problemas de Euler.
Aqui está uma otimização simples do seu método que não é exatamente a peneira de eatóstenes, mas é muito fácil de implementar: primeiro tente dividir x por 2 e 3, depois loop sobre j = 1..sqrt (x)/6, tentando dividir por 6*J-1 e 6*J+1. Isso pula automaticamente em todos os números divisíveis por 2 ou 3, ganhando uma aceleração de fator constante bastante agradável.
Tendo em mente os seguintes fatos (de Mathschallenge.net):
- Todos os primos, exceto 2, são estranhos.
- Todos os primos maiores que 3 podem ser escritos na forma 6k - 1 ou 6k + 1.
- Você não precisa verificar além da raiz quadrada de n
Aqui está a função C ++ que eu uso para n relativamente pequeno:
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)
}
Você provavelmente poderia pensar em mais otimizações próprias.
Eu recomendo Teste de Primalidade de Fermat. É um teste probabilístico, mas é correto surpreendentemente com frequência. E é incrivelmente rápido quando comparado com a peneira.
Para números razoavelmente pequenos, x%n para até SQRT (x) é muito rápido e fácil de codificar.
Melhorias simples:
Teste 2 e apenas números ímpares.
Teste 2, 3 e múltiplos de 6 + ou - 1 (todos os primos que não 2 ou 3 são múltiplos de 6 +/- 1, então você está basicamente apenas pulando todos os números pares e todos os múltiplos de 3
Teste apenas os números primos (requer cálculo ou armazenamento de todos os primos até SQRT (x))
Você pode usar o método de peneira para gerar rapidamente uma lista de todos os primos até algum limite arbitrário, mas tende a ser intensivo em memória. Você pode usar os múltiplos de 6 truques para reduzir o uso da memória para 1/3 de um pouco por número.
Eu escrevi uma classe Prime simples (c#) que usa dois campos de bits para múltiplos de 6+1 e múltiplos de 6-1, então faz uma pesquisa simples ... e se o número que estou testando estiver fora dos limites da peneira, Em seguida, ele volta aos testes por 2, 3, e múltiplos de 6 +/ O princípio do beijo ataca novamente!
Escrevi uma classe Prime que usa uma peneira para pré-calcular os primos menores e depois depende de testes por 2, 3 e múltiplos de seis +/- 1 para aqueles fora do alcance da peneira.
Para o Projeto Euler, ter uma lista de primos é realmente essencial. Eu sugiro manter uma lista que você usa para cada problema.
Eu acho que o que você está procurando é o Peneira de eratóstenes.
Seu direito, o simples é o mais lento. Você pode otimizá -lo um pouco.
Olhe para o uso do módulo em vez de raízes quadradas. Acompanhe seus primos. Você só precisa dividir 7 por 2, 3 e 5, pois 6 é um múltiplo de 2 e 3 e 4 é um múltiplo de 2.
Rslite mencionou o Eanthenos Sieve. É bastante direto. Eu tenho isso em vários idiomas em casa. Adicione um comentário se quiser que eu poste esse código mais tarde.
Aqui está o meu C ++. Ele tem muito espaço para melhorar, mas é rápido em comparação com as versões de idiomas dinâmicos.
// 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;
}
Vou vomitar o código Perl e Python que tenho assim que o encontrar. Eles são semelhantes em estilo, apenas menos linhas.
Aqui está um teste de primalidade simples em 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);
}
Também estou trabalhando através dos problemas do projeto Euler e, de fato, acabamos de terminar o número 3 (por ID), que é a busca pelo fator principal mais alto de um número composto (o número no? 600851475143).
Eu olhei para todas as informações sobre os primos (as técnicas de peneira já mencionadas aqui) e a fatoração inteira na Wikipedia e criei um algoritmo de divisão de teste de força bruta que decidi que faria.
Então, enquanto estou fazendo os problemas de Euler para aprender Ruby, eu estava olhando para codificar meu algoritmo e tropeçaram na biblioteca Mathn, que tem um Prime Class e um Classe inteira com uma prime_division método. quão legal é isso. Consegui obter a resposta correta para o problema com este snippet de rubi:
require "mathn.rb"
puts 600851475143.prime_division.last.first
Este snippet produz a resposta correta para o console. É claro que acabei fazendo uma tonelada de leitura e aprendizado antes de tropeçar nessa pequena beleza, pensei em compartilhar com todos ...
Eu gosto deste código 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]
Uma variante disso pode ser usada para gerar os fatores de um número.
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
Obviamente, se eu estivesse considerando um lote de números, não recalcularia o cache; Eu faria isso uma vez e fazia pesquisas nele.
Is not optimized but it's a very simple function.
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;
}
Maybe this implementation in Java can be helpful:
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)
}
}
The AKS prime testing algorithm:
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;
another way in python is:
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()
