Existe-t-il un algorithme simple permettant de déterminer si X est premier et de ne pas confondre un simple programmeur mortel?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai essayé de me frayer un chemin à travers le projet Euler et j'ai remarqué quelques problèmes qui vous demandaient de déterminer un nombre premier.
-
Je sais que je peux diviser x par 2, 3, 4, 5, ..., racine carrée de X et que si j'atteins la racine carrée, je peux (en toute sécurité) supposer que le nombre est premier . Malheureusement, cette solution semble assez compliquée.
-
J'ai examiné de meilleurs algorithmes pour déterminer si un nombre est premier, mais soyez confus rapidement.
Existe-t-il un algorithme simple permettant de déterminer si X est premier et de ne pas confondre un simple programmeur mortel?
Merci beaucoup!
La solution
Le premier algorithme est assez bon et beaucoup utilisé sur Project Euler. Si vous connaissez le nombre maximum que vous souhaitez, vous pouvez également rechercher le tamis d'Eratosthène.
Si vous conservez la liste des nombres premiers, vous pouvez également préciser le premier algo à diviser uniquement avec des nombres premiers jusqu'à la racine carrée du nombre.
Avec ces deux algorithmes (division et tamis), vous devriez pouvoir résoudre les problèmes.
Modifier : nom fixe, comme indiqué dans les commentaires
Autres conseils
Générer tous les nombres premiers inférieurs à une limite Sieve of Eratosthenes (la page contient des variantes dans 20 langages de programmation) est la solution la plus ancienne et la plus simple.
En 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
Exemple:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Je vois que le test de primalité de Fermat a déjà été suggéré, mais je travaille avec Structure et interprétation des programmes informatiques , ainsi que Miller-Rabin test (voir Section 1.2.6, problème 1.28) comme autre alternative. Je l'utilise avec succès pour les problèmes d'Euler.
Voici une optimisation simple de votre méthode qui n'est pas tout à fait le tamis d'Eratosthène mais qui est très facile à mettre en œuvre: essayez d'abord de diviser X par 2 et 3, puis passez en boucle sur j = 1..sqrt (X) / 6, en essayant de diviser par 6 * j-1 et 6 * j + 1. Cela saute automatiquement tous les nombres divisibles par 2 ou 3, ce qui vous procure une très belle accélération constante du facteur.
Gardez à l'esprit les faits suivants (tirés de MathsChallenge.net ) :
- Tous les nombres premiers sauf 2 sont impairs.
- Tous les nombres premiers supérieurs à 3 peuvent être écrits sous la forme 6k - 1 ou 6k + 1.
- Vous n'avez pas besoin de vérifier au-delà de la racine carrée de n
Voici la fonction C ++ que j'utilise pour n relativement petit:
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)
}
Vous pourriez probablement penser à davantage d’optimisations personnelles.
Je recommanderais le le test de primalité de Fermat . C'est un test probabiliste, mais il est correct étonnamment souvent. Et il est incroyablement rapide par rapport au tamis.
Pour des nombres assez petits, x% n pour jusqu’à sqrt (x) est extrêmement rapide et facile à coder.
Améliorations simples:
testez 2 et les nombres impairs uniquement.
test 2, 3, et multiples de 6 + ou - 1 (tous les nombres premiers autres que 2 ou 3 sont des multiples de 6 +/- 1, vous sautez donc essentiellement tous les nombres pairs et tous les multiples de 3
tester uniquement les nombres premiers (nécessite de calculer ou de stocker tous les nombres premiers jusqu'à sqrt (x))
Vous pouvez utiliser la méthode sieve pour générer rapidement une liste de tous les nombres premiers, jusqu’à une limite arbitraire, mais elle nécessite généralement beaucoup de mémoire. Vous pouvez utiliser l’astuce des multiples de 6 pour réduire l’utilisation de la mémoire à 1/3 de bit par nombre.
J'ai écrit une classe première simple (C #) qui utilise deux champs de bits pour des multiples de 6 + 1 et des multiples de 6-1, puis effectue une recherche simple ... et si le nombre que je teste est en dehors des limites de le tamis, alors il retombe sur les tests par 2, 3 et des multiples de 6 +/- 1. J'ai constaté que générer un tamis de grande taille prend plus de temps que de calculer les nombres premiers à la volée pour la plupart des problèmes que j'ai résolus jusque là. Le principe KISS frappe à nouveau!
J'ai écrit une classe de base qui utilise un tamis pour pré-calculer des nombres premiers plus petits, puis repose sur des tests effectués par 2, 3 et des multiples de six +/- 1 pour ceux situés en dehors de la plage du tamis.
Pour Project Euler, disposer d’une liste de nombres premiers est vraiment essentiel. Je suggère de maintenir une liste que vous utilisez pour chaque problème.
Je pense que vous recherchez le tamis d'Eratosthenes .
Votre droit les simples est le plus lent. Vous pouvez l'optimiser un peu.
Cherchez à utiliser le module au lieu de racines carrées. Gardez une trace de vos nombres premiers. il suffit de diviser 7 par 2, 3 et 5, car 6 est un multiple de 2 et 3, et 4 est un multiple de 2.
Rslite a mentionné le tamis eranthenos . C'est assez simple. Je l'ai en plusieurs langues à la maison. Ajoutez un commentaire si vous souhaitez que je publie ce code ultérieurement.
Voici mon C ++. Il reste encore beaucoup à faire pour l’améliorer, mais il est rapide par rapport aux versions à langages dynamiques.
// 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;
}
Je vais lancer le code Perl et python que j’ai dès que je le trouve. Ils sont similaires dans le style, juste moins de lignes.
Voici un test de primalité simple en 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);
}
Je travaille également sur les problèmes du projet Euler et, en fait, je viens juste de terminer n ° 3 (par id), qui est la recherche du facteur premier le plus élevé d’un nombre composé (le nombre dans le? est 600851475143).
J'ai consulté toutes les informations sur les nombres premiers (les techniques de tamisage déjà mentionnées ici), ainsi que sur la factorisation des nombres entiers sur wikipedia et suis parvenue à un algorithme de division d'essais en force brute que j'ai décidé de faire.
Alors que je me préoccupais beaucoup d’apprendre ruby, j’ai cherché à coder mon algorithme et suis tombé par hasard sur la bibliothèque mathn qui a un Classe primordiale et un Classe entière avec une méthode prime_division . à quel point cela est cool. J'ai pu obtenir la réponse correcte au problème avec cet extrait de rubis:
require "mathn.rb"
puts 600851475143.prime_division.last.first
cet extrait envoie la réponse correcte à la console. Bien sûr, j'ai fini par lire et apprendre avant de tomber sur cette petite beauté, je pensais juste que je la partagerais avec tout le monde ...
J'aime ce code 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]
Une variante de ceci peut être utilisée pour générer les facteurs d’un nombre.
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
Bien sûr, si je factorisais un lot de nombres, je ne recalculerais pas le cache; Je le ferais une fois et y ferais des recherches.
N’est pas optimisé, mais c’est une fonction très simple.
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;
}
Peut-être que cette implémentation en Java peut être 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'algorithme de test principal 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;
Une autre façon en python est:
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()
