Sujet Précédent Sujet Suivant

FORMULES POUR NOMBRES PREMIERS

mirana88 Messages postés 1 Date d'inscription dimanche 1 août 2010 Statut Membre Dernière intervention 1 août 2010 - 1 août 2010 à 17:26
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 17 août 2010 à 21:26

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/52130-formules-pour-nombres-premiers

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
17 août 2010 à 21:26

Après avoir beaucoup utilisé ces logiciels, j'ai fait quelques perfectionnements mais j'ai surtout ajouté dans le zip et le manuel de l'utilisateur des formules déjà publiées que j'ai pu facilement retrouver et quelques autres dont je ne trouve aucune trace sur Internet, ainsi que leurs vérification.

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
11 août 2010 à 21:43

J'ai effectué une mise à jour en profondeur avec quelques changements de méthodes qui apportent de bien meilleures performances. Les commentaires ont été clarifiés. Le manuel de l'utilisateur est plus commode. La recherche de nouvelles formules est facilitée.

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
10 août 2010 à 18:17

=> Alain Proviste : je n'ai pas programmé cette autre idée. Mais supposons que l'on souhaite travailler avec les 1 000 000 premiers nombres premiers. Le 1 000 000-ième est 15 485 863. Si on prend un vecteur v[i] de 15 485 864 octets que l'on met à 0 ou 1 après avoir calculé les nombres premiers avec un programme comme le mien ou avec le crible d'Ératosthène, alors pour savoir si n est premier il suffit de voir si v[n] vaut 0 ou 1. Cette idée simple devrait être utilisable au moins dans certains cas.

cs_Alain Proviste Messages postés 908 Date d'inscription jeudi 26 juillet 2001 Statut Modérateur Dernière intervention 1 février 2015 2
10 août 2010 à 17:16

peux tu illustrer ton dernier commentaire avec un exemple ?

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
10 août 2010 à 14:37

Pour aller plus vite et plus loin dans la recherche de nouvelles formules on a besoin d'un moyen beaucoup plus rapide pour savoir si n est premier ou composé. Alors, il y a une méthode très simple pour cela, c'est de marquer une fois pour toutes le n-ième octet d'une suite d'octets à 0 ou 1 après avoir calculé la suite des nnp premiers nombres premiers. On peut aussi envisager seulement une suite de bits. Ce n'est pas économique en place mémoire, mais pourquoi pas essayer ? Ce sera peut-être un autre programme tout différent.

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
7 août 2010 à 23:24

La routine prems() qui calcule les nnp premiers nombres premiers va maintenant trois fois plus vite. J'ai mis beaucoup de commentaires parce qu'elle est plus difficile à comprendre. L'ancienne est jointe sous le nom de old_prems.cpp

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
5 août 2010 à 22:07

Merci Alain Proviste. Après quelques essais j'ai amélioré un peu la vitesse des calculs. Et maintenant, formules.exe prépare en plus un fichier verif.bat pour aider à lancer la vérification.

cs_Alain Proviste Messages postés 908 Date d'inscription jeudi 26 juillet 2001 Statut Modérateur Dernière intervention 1 février 2015 2
5 août 2010 à 18:46

C'est du bon travail et c'est interessant.

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
3 août 2010 à 17:41

Pour faciliter les recherches j'ai mis les paramètres nnp, i1, ... ,m2 dans l'appel de formules.exe et non plus à l'intérieur. Et j'ai ajouté le temps d'exécution. La formule p = n3 -35n2 + 308n +73 fournit successivement 29 nombres premiers pour n de 0 à 28 et en fournit 74 pour n de 0 à 100. C'est bien !

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
2 août 2010 à 21:58

Dans la formule : p = i*n4 + j*n3 + k*n2 + l*n + m on a p = m pour n = 0. Donc m est nécessairement dans la liste calculée des nombres premiers. Ce qui permet de ne pas essayer les autes valeurs de m entre m1 et m2. Ceci fait gagner beaucoup de temps.

pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 11
2 août 2010 à 18:12

J'ai ajouté dans le zip des fichiers commentés formules_*.txt qui affichent des formules obtenues en divers temps de calcul avec divers jeux de paramètres limites pour les recherches demandées. Ceci permet de montrer ce que l'on peut obtenir en faisant divers choix pour : max, i1, i2, j1, ... , m2.

Discussions similaires

Nombre Premier

Traduction d'un nombre reel en chiffres en arabe

convertir chiffres romains en nombre arabe

decomposition d'un nombre en java

Écrivez un programme Java (Premiers.java) qui permet d'afficher

Votre réponse

Discussions similaires