Question d'entrevue: Quelle est la façon la plus rapide de générer des nombres premiers de façon récursive? [fermé]
Génération de nombre premier est simple, mais quel est le moyen le plus rapide de le trouver et de générer( nombres premiers) récursivement ?
voici ma solution. Cependant, il n'est pas le meilleur moyen. Je pense que c'est O(N*sqrt(N)). Veuillez me corriger si je me trompe.
public static boolean isPrime(int n) {
if (n < 2) {
return false;
} else if (n % 2 == 0 & n != 2) {
return false;
} else {
return isPrime(n, (int) Math.sqrt(n));
}
}
private static boolean isPrime(int n, int i) {
if (i < 2) {
return true;
} else if (n % i == 0) {
return false;
} else {
return isPrime(n, --i);
}
}
public static void generatePrimes(int n){
if(n < 2) {
return ;
} else if(isPrime(n)) {
System.out.println(n);
}
generatePrimes(--n);
}
public static void main(String[] args) {
generatePrimes(200);
}
5 réponses
pour la récidive, vous devez utiliser memoization pour améliorer votre fonction récursive, signifie Si vous trouvez le nombre premier enregistrer dans le tableau, et dans l'appel à isPrime(n) vérifier d'abord le nombre existe dans le tableau si non appeler à isPrime(n, (int) Math.sqrt (n)). aussi si isPrime (n,i) retourne true, add it to prime list, c'est mieux que votre tableau soit trié pour faire de la recherche binaire, en C# il y a une liste triée, et une opération de recherche binaire [faire une liste de n élément prend O(n log n) et la recherche est O(log(n))] je ne savais pas à propos de java [mais vous pouvez la mettre en œuvre].
Edit: votre approche actuelle est O(n sqrt(n)) mais avec mon approche, il peut être dans le même ordre! mais de meilleures performances, en fait l'ordre est O(n sqrt(n) / log (n) + n log(n/log(n))) et parce que log(n) est plus petit que n^Epsilon , il est préférable de dire que c'est O(n sqrt(n)) mais comme vous pouvez le voir, il va courir log(n) PLUS VITE.
aussi c'est mieux faire i-2 pas moi-- et quelques vérifications supplémentaires au démarrage pour exécuter l'algorithme 2 * log (n) plus rapidement.
en mathématiques, le tamis D'Atkin est un algorithme rapide et moderne pour trouver tous les nombres premiers jusqu'à un entier spécifié.
article Wikipedia (contient un pseudo)
pour aborder le fait de faire cela récursivement, peut-être le tamis de Eratosthenes peut être mis en œuvre récursivement. Ce page pourrait être utile, car il semble discuter d'un récursive de la mise en œuvre.
ce dont vous avez besoin est le tamis de Forever, voici le code pour un testeur de premier récursif, je pense qu'il est assez efficace parce qu'il n'a besoin de tester les facteurs principaux, faites-moi savoir ce que vous en pensez;)
au fait, je ne voudrais pas essayer avec quelque chose au-dessus d'un octet, ça semble prendre un moment avec quelque chose au-dessus de 100.
public boolean isPrime(byte testNum)
{
if ( testNum <= 1 )
return false;
for ( byte primeFactor = 2; primeFactor < testNum; primeFactor++ )
if ( isPrime(primeFactor) )
if ( testNum % primeFactor == 0 )
return false;
return true;
}
D'abord, si vous voulez générer grands nombres premiers (par opposition à des nombres entiers de test pour la primalité) alors le théorème de Pocklington est pratique. Ce théorème permet un test de primalité rapide pour un candidat p Si vous connaissez assez de facteurs premiers de p-1. Par conséquent, la méthode suivante est possible: Générenerate quelques nombres premiers, calculer un multiple approprié de leur produit et de tester en utilisant le théorème de Pocklington. Si vous voulez trouver de grands nombres premiers (par exemple pour le cryptosystème RSA) alors vous devrez appliquer cette méthode récursivement pour générer les facteurs de p-1.
la description ci-dessus manque de nombreux détails. Mais la méthode a été analysé en profondeur. Je pense que cet article était le la méthode la plus rapide quand si a été publié, bien que quelque temps est passé depuis lors et quelqu'un aurait pu l'améliorer.
P. Mihailescu. "Fast Generation of Provable Primes using Search in Arithmetic Progressions", Proceedings CRYPTO 94, Lecture Notes in Computer Science vol 939, Springer 1994, pp.
pourquoi récursivement?
utilisez un meilleur algorithme de génération de nombres premiers comme tamis D'Eratosthènes ou encore mieux tamis D'Atkin.