Esiste un semplice algoritmo che può determinare se X è primo e non confondere un semplice programmatore mortale?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho cercato di farmi strada attraverso Project Euler e ho notato una manciata di problemi che ti chiedono di determinare un numero primo come parte di esso.
-
So che posso semplicemente dividere x per 2, 3, 4, 5, ..., radice quadrata di X e se arrivo alla radice quadrata, posso (tranquillamente) presumere che il numero sia primo . Sfortunatamente questa soluzione sembra abbastanza klunky.
-
Ho cercato algoritmi migliori su come determinare se un numero è primo, ma mi confondo velocemente.
Esiste un semplice algoritmo che può determinare se X è primo e non confondere un semplice programmatore mortale?
Grazie mille!
Soluzione
Il primo algoritmo è abbastanza buono e molto usato su Project Euler. Se conosci il numero massimo che desideri, puoi anche cercare il setaccio di Eratostene.
Se mantieni l'elenco dei numeri primi puoi anche affinare il primo algo da dividere solo con i numeri primi fino alla radice quadrata del numero.
Con questi due algoritmi (divisione e setaccio) dovresti essere in grado di risolvere i problemi.
Modifica : nome fisso come indicato nei commenti
Altri suggerimenti
Per generare tutti i numeri primi meno di un limite Sieve of Eratosthenes (la pagina contiene varianti in 20 linguaggi di programmazione) è la soluzione più antica e più semplice.
In 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
Esempio:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Vedo che il test di primalità di Fermat è già stato suggerito, ma ho lavorato su Struttura e interpretazione dei programmi per computer e forniscono anche il Miller-Rabin test (vedere Sezione 1.2.6, problema 1.28) come altra alternativa. L'ho usato con successo per i problemi di Eulero.
Ecco una semplice ottimizzazione del tuo metodo che non è proprio il setaccio di Eratostene ma è molto facile da implementare: prima prova a dividere X per 2 e 3, quindi passa sopra j = 1..sqrt (X) / 6, cercando di dividere per 6 * j-1 e 6 * j + 1. Questo salta automaticamente su tutti i numeri divisibili per 2 o 3, ottenendo una piacevole accelerazione costante dei fattori.
Tenendo presente i seguenti fatti (da MathsChallenge.net ) :
- Tutti i numeri primi tranne 2 sono dispari.
- Tutti i numeri primi maggiori di 3 possono essere scritti nella forma 6k - 1 o 6k + 1.
- Non è necessario controllare oltre la radice quadrata di n
Ecco la funzione C ++ che uso per n relativamente piccolo:
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)
}
Probabilmente potresti pensare a più ottimizzazioni tue.
Consiglierei Test di primalità di Fermat . È un test probabilistico, ma è spesso sorprendentemente corretto. Ed è incredibilmente veloce rispetto al setaccio.
Per numeri ragionevolmente piccoli, x% n fino a sqrt (x) è terribilmente veloce e facile da codificare.
Miglioramenti semplici:
solo test 2 e numeri dispari.
test 2, 3 e multipli di 6 + o - 1 (tutti i numeri primi diversi da 2 o 3 sono multipli di 6 +/- 1, quindi essenzialmente stai semplicemente saltando tutti i numeri pari e tutti i multipli di 3
verifica solo numeri primi (richiede il calcolo o la memorizzazione di tutti i numeri primi fino a sqrt (x))
È possibile utilizzare il metodo sieve per generare rapidamente un elenco di tutti i numeri primi fino a un limite arbitrario, ma tende a richiedere molta memoria. Puoi usare i multipli di 6 trick per ridurre l'utilizzo della memoria fino a 1/3 di bit per numero.
Ho scritto una semplice classe primaria (C #) che utilizza due bitfield per multipli di 6 + 1 e multipli di 6-1, quindi esegue una semplice ricerca ... e se il numero che sto testando è fuori dai limiti di il setaccio, quindi ricade sui test di 2, 3 e multipli di 6 +/- 1. Ho scoperto che la generazione di un setaccio grande richiede in realtà più tempo rispetto al calcolo dei numeri primi al volo per la maggior parte dei problemi di eulero che ho risolto finora. Il principio KISS colpisce ancora!
Ho scritto una classe primaria che utilizza un setaccio per pre-calcolare numeri primi più piccoli, quindi fa affidamento su test di 2, 3 e multipli di sei +/- 1 per quelli al di fuori del campo di validità del setaccio.
Per Project Euler, avere un elenco di numeri primi è davvero essenziale. Suggerirei di mantenere un elenco che usi per ogni problema.
Penso che quello che stai cercando sia Sieve of Eratosthenes .
Il tuo diritto, il semplice è il più lento. Puoi ottimizzarlo un po '.
Cerca di utilizzare il modulo anziché le radici quadrate. Tieni traccia dei tuoi numeri primi. devi solo dividere 7 per 2, 3 e 5 poiché 6 è un multiplo di 2 e 3 e 4 è un multiplo di 2.
Rslite ha menzionato il eranthenos sieve . È abbastanza semplice. Ce l'ho in diverse lingue a casa. Aggiungi un commento se vuoi che pubblichi quel codice in un secondo momento.
Ecco il mio C ++. Ha molto spazio per migliorare, ma è veloce rispetto alle versioni linguistiche dinamiche.
// 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;
}
Lancerò il codice Perl e Python che ho non appena lo trovo. Sono simili nello stile, solo meno linee.
Ecco un semplice test di primalità in 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);
}
Sto lavorando anche ai problemi del Project Euler e in effetti ho appena finito il n. 3 (per id) che è la ricerca del fattore primo più alto di un numero composto (il numero nel? è 600851475143).
Ho guardato tutte le informazioni sui numeri primi (le tecniche del setaccio già menzionate qui) e sulla fattorizzazione dei numeri interi su Wikipedia e ho trovato un algoritmo di divisione della prova di forza bruta che ho deciso di fare.
Quindi, mentre sto facendo i problemi di eulero per imparare il rubino, stavo cercando di programmare il mio algoritmo e mi sono imbattuto nella libreria matematica che ha un classe Prime e un Classe intera con un metodo prime_division . quant'è fico. sono stato in grado di ottenere la risposta corretta al problema con questo frammento di ruby:
require "mathn.rb"
puts 600851475143.prime_division.last.first
questo frammento restituisce la risposta corretta alla console. ovviamente ho finito per leggere un sacco di cose prima di imbattermi in questa piccola bellezza, ho pensato di condividerla con tutti ...
Mi piace questo codice 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]
Una variante di questo può essere usata per generare i fattori di un numero.
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
Ovviamente, se facessi il factoring di un batch di numeri, non ricalcolerei la cache; Lo farei una volta e farei delle ricerche.
Non è ottimizzato ma è una funzione molto semplice.
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;
}
Forse questa implementazione in Java può essere utile:
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)
}
}
L'algoritmo di test Prime di 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;
un altro modo in 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()
