Nombres premiers (RAM / Vitesse)
Résolu/Fermé
Utilisateur anonyme
-
Modifié par EchoIsON le 23/03/2016 à 18:28
Utilisateur anonyme - 26 mars 2016 à 17:20
Utilisateur anonyme - 26 mars 2016 à 17:20
A voir également:
- Nombres premiers (RAM / Vitesse)
- Vitesse processeur - Guide
- Augmenter vitesse pc windows 10 - Guide
- Test vitesse ssd - Guide
- Test vitesse pc - Guide
- Mon pc ram - Guide
1 réponse
Franck7511
Messages postés
14296
Date d'inscription
jeudi 24 décembre 2009
Statut
Membre
Dernière intervention
10 août 2017
1 121
Modifié par Franck7511 le 23/03/2016 à 23:03
Modifié par Franck7511 le 23/03/2016 à 23:03
Pour ton problème, tu peux "raccourcir" ta table d'Eratosthène en utilisant le postulat de Bertrand: https://en.wikipedia.org/wiki/Bertrand%27s_postulate
Regarde la partie "Better results" pour des résultats encore plus optimisés...
Au lieu de stocker un tableau de 1 à X (où X est l'entrée de l'utilisateur), tu peux aller de 1 à sqrt(X) puis de X/2 à X (ou bien mieux si X est assez grand !), d'où l'économie de mémoire conséquente (tu peux faire deux tableaux)
L'idée est de faire exactement comme le critère d'Eratosthène normal mais en excluant la partie inutile, donc ça sera encore plus rapide car moins de données à traiter.
Une idée assez immédiate est de virer les nombres pairs, tu peux économiser la moitié de ta mémoire.
Ceci dit, cet algorithme ne se prête pas très bien au Multithreading mais ça reste possible visiblement... J'ai trouvé ça : https://mmfcordeiro.files.wordpress.com/2012/10/mmfcordeiro-parallelization-of-the-sieve-of-eratosthenes.pdf
Si tu connais déjà les nombres premiers entre 1 et sqrt(X) c'est faisable facilement en parallèle sur l'autre tableau (X/2 -> X)...
PS: C'est exactement l'"Optimization 2" qu'ils proposent...
Regarde la partie "Better results" pour des résultats encore plus optimisés...
Au lieu de stocker un tableau de 1 à X (où X est l'entrée de l'utilisateur), tu peux aller de 1 à sqrt(X) puis de X/2 à X (ou bien mieux si X est assez grand !), d'où l'économie de mémoire conséquente (tu peux faire deux tableaux)
L'idée est de faire exactement comme le critère d'Eratosthène normal mais en excluant la partie inutile, donc ça sera encore plus rapide car moins de données à traiter.
Une idée assez immédiate est de virer les nombres pairs, tu peux économiser la moitié de ta mémoire.
Ceci dit, cet algorithme ne se prête pas très bien au Multithreading mais ça reste possible visiblement... J'ai trouvé ça : https://mmfcordeiro.files.wordpress.com/2012/10/mmfcordeiro-parallelization-of-the-sieve-of-eratosthenes.pdf
Si tu connais déjà les nombres premiers entre 1 et sqrt(X) c'est faisable facilement en parallèle sur l'autre tableau (X/2 -> X)...
PS: C'est exactement l'"Optimization 2" qu'ils proposent...
26 mars 2016 à 17:20