Trouver la liste des nombres premiers dans les plus brefs délais
J'ai lu beaucoup de nombreux algorithmes pour trouver des nombres premiers et la conclusion est qu'un nombre est un nombre premier s'il n'est pas divisible par l'un de ses précédents nombres premiers.
Je ne suis pas en mesure de trouver une définition plus précise. Basé sur ce que j'ai écrit un code et il fonctionne satisfaisante jusqu'le nombre max je passe est 1000000. Mais je crois qu'il y a beaucoup plus rapide des algorithmes pour trouver tous les nombres premiers inférieur à un nombre donné.
Voici mon code, je peux avoir une meilleure version de la même chose?
public static void main(String[] args) {
for (int i = 2; i < 100000; i++) {
if (checkMod(i)) {
primes.add(i);
}
}
}
private static boolean checkMod( int num) {
for (int i : primes){
if( num % i == 0){
return false;
}
}
return true;
}
Avez-vous essayé de chercher sur le site? Il y a une tonne de questions sur le premier numéro de trouver des algorithmes.
oui j'ai trouvé une solution ici stackoverflow.com/questions/3808171/... Mais quelque part, il n'est pas bien expliqué et je crois que c'est compliqué 🙁
codereview.stackexchange.com
oui j'ai trouvé une solution ici stackoverflow.com/questions/3808171/... Mais quelque part, il n'est pas bien expliqué et je crois que c'est compliqué 🙁
codereview.stackexchange.com
OriginalL'auteur dharam | 2012-05-21
Vous devez vous connecter pour publier un commentaire.
La bonne chose dans votre test de primalité est que vous n'diviser par des nombres premiers.
La mauvaise chose est que vous divisez par tous nombres premiers trouvés jusqu'à présent, c'est, de tous les nombres premiers plus petits que le candidat. Cela signifie que, pour le plus grand nombre premier inférieur à un million de dollars, 999983, vous divisez par 78497 premiers à savoir que ce nombre est un nombre premier. C'est beaucoup de travail. Tellement, en fait, que le travail passé sur les nombres premiers dans cet algorithme représente environ 99,9% de tous les travaux, quand on va à un million de dollars, une grande partie pour des limites plus élevées. Et que l'algorithme est presque quadratique, pour trouver les nombres premiers à
n
de cette façon, vous devez effectuer surdivisions.
Une simple amélioration est d'arrêter la division antérieure. Laissez
n
être un nombre composé (c'est à dire un nombre greter que 1 qui a d'autres diviseurs que 1 etn
), et laissezd
être un diviseur den
.Maintenant,
d
être un diviseur den
signifie quen/d
est un entier, et aussi un diviseur den
:n/(n/d) = d
.On peut donc naturellement le groupe des diviseurs de
n
en paires, chaque diviseurd
donne lieu à la paire(d, n/d)
.Pour une telle paire, il y a deux possibilités:
d = n/d
, ce qui signifien = d²
, oud = √n
.d < n/d
. Mais qui traduit immédiatement àd² < n
oud < √n
.Donc, de toute façon, chaque paire de diviseurs contient (au moins) l'un n'excédant pas
√n
, par conséquent, sin
est un nombre composé, son plus petit diviseur (autre que 1) ne dépasse pas√n
.Afin que nous puissions arrêter la division de première instance lorsque nous avons atteint
√n
:Remarque: cela dépend de la liste des nombres premiers itérée dans l'ordre croissant. Si cela n'est pas garanti par la langue, vous devez utiliser une autre méthode, itérer par l'indice par le biais d'un
ArrayList
ou quelque chose comme ça.L'arrêt de la division de première instance à la racine carrée du candidat, pour le plus grand nombre premier inférieur à un million de dollars, 999983, nous avons maintenant seulement besoin de le diviser par le 168 nombres premiers en dessous de 1000. C'est beaucoup moins de travail qu'auparavant. L'arrêt de la division de première instance à la racine carrée, et en divisant uniquement par les nombres premiers, est aussi bonne que la division de première instance peut éventuellement obtenir et nécessite environ
divisions, pour
n = 1000000
, c'est un facteur d'environ 750, pas mal, est-il?Mais c'est pas encore très efficace, les méthodes les plus efficaces pour trouver tous les nombres premiers ci-dessous
n
sont des passoires. Simple à mettre en œuvre est la classique Crible d'Eratosthène. Qui trouve les nombres premiers ci-dessousn
en O(n*log log n) opérations, avec quelques améliorations (en éliminant les multiples de plusieurs petits nombres premiers de considération à l'avance), sa complexité peut être réduite à O(n) opérations. Un relativement nouveau tamis avec un meilleur comportement asymptotique est le Crible d'Atkin, qui trouve que les premiers àn
en O(n) opérations, ou par l'amélioration de l'élimination de l'multiples de certains petits nombres premiers, en O(n/log log n) opérations.Le Crible d'Atkin est plus compliqué à mettre en œuvre, il est donc probable qu'une bonne mise en œuvre d'un Crible d'Eratosthène effectue de mieux qu'un naïf mise en œuvre d'un Crible d'Atkin. Pour les implémentations de l', comme l'optimisation des niveaux, la différence de performances est faible, à moins que la limite devient grand (plus grand que 1010; et il n'est pas rare que, dans la pratique, un Crible d'Eratosthène échelles de mieux qu'un Crible d'Atkin-delà, en raison d'un meilleur accès à la mémoire). Alors je vous recommandons de commencer avec un Crible d'Eratosthène, et seulement si sa performance n'est pas satisfaisante, en dépit des efforts honnêtes à l'optimisation, de la plonger dans le Crible d'Atkin. Ou, si vous ne voulez pas mettre en œuvre vous-même, trouver un bon de mise en œuvre de quelqu'un d'autre a déjà sérieusement à l'écoute.
Je suis allé dans un peu plus en détail dans une réponse avec un peu différente, où le problème a été de trouver le n-ième nombre premier. Certaines implémentations de la plus-ou-moins efficaces méthodes sont liées à partir de cette réponse, en particulier une ou deux utilisables (mais pas beaucoup optimisé) implémentations d'un Crible d'Eratosthène.
(3/4)*(1000000^0.5) = 750. 🙂
Oh, merde, je devrais vraiment prendre le temps de l'écrire sur le papier. Merci.
OriginalL'auteur Daniel Fischer
J'ai toujours utiliser le crible d'ératosthène:
J'espère que vous comprenez mes commentaires
OriginalL'auteur gabitzish
Je comprends un nombre premier à être un certain nombre qui est divisible par lui-même et le nombre 1 (sans reste). Voir Article De Wikipedia
Cela étant dit, je ne comprends pas l'algorithme très bien dans le deuxième commentaire, mais une petite amélioration à votre algorithme serait de changer votre boucle for pour:
Ceci est basé sur l'hypothèse que 1, 2, et 3 sont tous les nombres premiers et tous les nombres pairs, par la suite, ne sont pas des nombres premiers. Ce qui réduit votre algorithme en deux.
OriginalL'auteur Benjamin Oman
Je veux le faire encore légèrement version améliorée de la 0ne proposé par Benjamin Oman ci-dessus,
C'est juste une modification pour éviter de vérifier primalité de tous les nombres se terminant avec le chiffre '5', parce que ces chiffres ne sont certainement pas les premiers que ces sont divisibles par 5.
Ceci est basé sur l'hypothèse que 2,3,5 sont des nombres premiers. La au-dessus de peu de changement permettra de réduire tous les facteurs de 5 et de s'améliorer.
primes
initialisé? Elle contient tous les numéros, comme 2, 3 et 5?OriginalL'auteur user3261848
Joliment expliqué par @Daniel Fischer.
Une mise en Œuvre en C++ à partir de son explication:
OriginalL'auteur Love Sharma