Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

A propos des nombres premiers

Posté par
YgipupCH
07-06-13 à 09:00

Bonjour tout le monde

Cela fait longtemps que je m'amuse avec les nombres premiers, mais là, je cherche à programmer un algorithme "allégé". Et pour y parvenir, j'applique une formule simple mais qui semble efficace. Mais d'abord, un petit récapitulatif en image:

A propos des nombres premiers

Posté par
YgipupCH
A propos des nombres premiers suite... 07-06-13 à 09:20

Donc, j'applique le filtre standard des 60%, ce qui simplifie les recherches (pas besoin de chercher les modulo de 2 & 5...), et là, sur cette table simplifiée, je pose ma formule, mais que je ne saurais formuler exactement, à savoir:
Me référant à une table de nombres premiers "complète" (ici => 97), je peux garantir la recherche de tout nombre premiers se situant dans la limite max (LM pour la suite...) de la table de référence jusqu'à 2LM-1 (ici => 193). Ce qui veut dire que tout nombre indivisible entre 97 et 193 est un nombre premier.

Cette affirmation est-elle juste => l'infini?

Et une autre affirmation à vérifier Soit un nombre à tester(NAT pour la suite), par exemple 157, je n'ai besoin d'effectuer les tests (modulo) que jusqu'à {Arrondi sup(NAT/2)}, soit par exemple 79 (cela m'économise quand même 3 tests à ce stade...)

Et j'en ai même une petite dernière, mais là, c'est purement spéculatif et inutile dans ma programmation
à savoir: entre LM et 2LM-1 il y aura toujours au minimum 1 nombre premier...
D'avance merci à tous ceux qui prendront le temps de me lire et peut-être même de me répondre

Posté par
LeHibou
re : A propos des nombres premiers 07-06-13 à 09:26

Bonjour,

Entre n et 2n, il existe toujours un nombre premier.
C'est un théorème de Bertrand, démontré par Tchebychev.

Posté par
plumemeteore
re : A propos des nombres premiers 07-06-13 à 09:32

Bonjour.
Un nombre est premier s'il n'est divisible par aucun nombre premier inférieur ou égal à sa racine carrée (ce qui est toutefois long à vérifier pour les très grands nombres).

Posté par
YgipupCH
re : A propos des nombres premiers 07-06-13 à 09:47

Merci pour tout LeHibou, je ne connaissais pas ces travaux, mais il faut dire aussi que je n'ai pas un niveau de math suffisant pour y comprendre quelque chose. Je suis plutôt vieille école, à savoir la recherche manuelle... Plein de tableurs différents pour afficher certaines récurrences, et surtout des résultats plus "graphiques" ou "design"

Merci aussi plumemeteore, et comme tu l'as si bien remarqué dans ta parenthèse, trop long, d'où l'autre idée: {Arrondi sup (NAT/2)}, qui devrait largement soulager le temps de calcul, même si cela en implique un petit peu plus que la racine carrée...

Posté par
ArgShX
re : A propos des nombres premiers 07-06-13 à 10:03

Bonjour,

Pour ta première affirmation je ne suis pas sûr de comprendre. Qu'apelles-tu un nombre indivisible ? Indivisible par quoi ?

Et pour la deuxième, soit j'ai rien compris, soit tu fais erreur. N/2 est largement supérieur à \sqrt{N}. Donc oui ça marche en faisant les calculs jusqu'à N/2, mais c'est une perte de temps monumentale.

Posté par
YgipupCH
re : A propos des nombres premiers 07-06-13 à 10:14

Bonjour ArgShx,
J'appelle un nombre indivisible tout nombre ne pouvant être divisé par les nombres premiers présents dans la table de référence.

Et pour la 2ème, c'est simplement que la majorité des langages de programmation que j'ai étudié ne fournissent pas de base la fonction racine, ou avec des annexes difficiles d'accès, surtout quand on approche les grands nombres. Donc, histoire de minimiser la boucle de recherche, je pensais utiliser cette formule, mais en effet, vu la différence grandissante entre N/2 et  \sqrt{N}, je vais de ce pas réviser ma programmation
Merci encore

Posté par
Surb
re : A propos des nombres premiers 07-06-13 à 12:09

Bonjour,

Dans mes souvenirs, une manière "simple" et efficace pour extraire la racine d'un nombre c et considérer la suite

 \\ \left\{\begin{array}{l} x_0 = 0\\
 \\ x_{k+1} = \frac{c+x_k}{1+x_k}, k = 0,1,2,...
 \\ \end{array}\right.
 \\
Jusqu'à ce que |x_k-x_{k+1}| < \epsilon, où \epsilon est une tolérance de calcul donnée. J'utilise \epsilon = 10^{-10} d'habitude mais c'est à toi de voir ce dont tu as besoin.

Posté par
YgipupCH
re : A propos des nombres premiers 07-06-13 à 13:03

Bonjour Surb,
Merci pour ces infos, mais là, déjà, je suis largué. La notation "complexe" des algorithmes comme tu la propose ici m'est plutôt inconnue, donc transposer ceci en un quelconque langage informatique .
En revanche, en n'utilisant que les opérations de base (+ - * /), j'ai plutôt pensé à "boucler ainsi le problème:
Si NAT < NP*NP alors j'effectue le test, sinon la boucle se termine et je passe au NAT suivant
(NAT => Nombre à tester / NP => Nombre premier utilisé pour le test en cours (issu de la table de réf))
Après tout, si je ne peux effectuer une racine sur l'un de mes membres, je peux faire ce test avec l'autre membre de mon test au carré, car cela reste booléen

Posté par
Surb
re : A propos des nombres premiers 07-06-13 à 13:57

Effectivement ta solution est d'autant plus simple.

Je ne sais pas quel language tu utilises, mais voici un pseudocode (au cas ou ):

INTPUT : c

tol = 10^(-10)
x = 0
x_old = 10
While |x-x_old| > tol
    x_old = x
    x = (c+x_old)/(1+x_old)
end

OUTPUT: x = c

Posté par
ArgShX
re : A propos des nombres premiers 07-06-13 à 14:18

Simple curiosité, quels langage(s) tu utilises ? Parce que des langages de prog sans racine facilement utilisable on en voit plus tellement (à mon humble connaissance qui est tout sauf exhaustive).

Posté par
YgipupCH
re : A propos des nombres premiers 07-06-13 à 14:29

Merci Surb

Je ne sais pas si j'arriverai à le retranscrire, mais pour sûr qu'un jour ou l'autre je testerai ces lignes de codes, histoire de comprendre le truc
Quand aux langages, je ne sais pas encore lequel je vais finir par choisir, étant donné certaines complexités rencontrées. Java, trop susceptible, même quand il s'agit de reprendre des lignes de code du net qui sont censées fonctionner. Je m'accroche encore un peu, mais je dérive déjà sur Ada, qui semble, en plus, être plus rapide que Java pour le traitement que je veux faire . Je me suis aussi intéressé à KPL, mais plus disponible, et le langage qui le remplace est payant
Ce qui est fun, c'est que j'ai appris dernièrement que j'avais déjà appris à programmer orienté objet avec le Basic, dont j'ai quelque peu gardé certaines habitudes procédurales .
Mais comme j'ai le temps d'apprendre à peu près n'importe quel langage, je test, je tâtonne et je développe certaines procédures sous diverses plateformes, dont les tableurs. Je suis preneur de toutes les infos au sujet des langages, car le mandat que je me suis fixé est simple et très complexe:
Dans la limite du PC, établir la plus grande table de nombres premiers possible (simple non)
La complexité réside avant tout dans le codage, car le principe de base est celui des grecs de l'antiquité, avec le défaut que plus la table de référence augmente plus il faut faire de test... à la main, ça va un moment, même si je ne teste que 40% des nombre

Posté par
YgipupCH
Un exemple de tableau de recherche 07-06-13 à 14:54

D'ailleurs, voici un petit exemple d'une de mes recherche. Facile à programmer (pour certains aspects seulement), il faudra néanmoins faire les recherches à la main, et si aucune puissance n'apparaît, c'est que le nombre est premier (modulo = 0). Je l'écris alors dans la prochaine colonne disponible, contenant toujours les même formules. Et sinon, ça reste un extracteur de facteurs assez sympa à réaliser .
C'est même un exercice qui peut aider les élèves à comprendre les nombres premiers , mais il faut aussi qu'ils soient ok avec la programmation du tableur...

Un exemple de tableau de recherche

Posté par
LeDino
re : A propos des nombres premiers 07-06-13 à 17:13

Citation :
Et pour la 2ème, c'est simplement que la majorité des langages de programmation que j'ai étudié ne fournissent pas de base la fonction racine, ou avec des annexes difficiles d'accès, surtout quand on approche les grands nombres.
D'abord ça m'étonnerait : la majorité des langages incluent la racine carrée.

Ensuite tu n'as nul besoin de la racine carré pour stopper ton algorithme de crible.
Au lieu de comparer ton compteur d'itération K avec racine(N) il te suffit de comparer K² avec N.
Et si ton langage de miséreux n'a pas de fonction "carré", tu fais comme à l'école :  K² = K * K  ...

Donc en résumé, on continue le crible :  TANT QUE  (K*K < N)  

Posté par
LeDino
re : A propos des nombres premiers 07-06-13 à 17:17

@YgipupCH:

Je viens de voir que dans tes messages suivants, tu as trouvé par toi même comment stopper la boucle en testant K*K < N.
Donc mon message précédent est caduque ...

Posté par
YgipupCH
re : A propos des nombres premiers 07-06-13 à 22:06

Bonsoir LeDino,
1: Merci à tous de rester courtois et poli sur le forum de façon à ce que le forum reste un lieu convivial et sympathique pour tous, élèves et correcteurs
     (Ceci est une recopie de la charte du forum )
2: Heureusement que tu as pris le temps de finir de lire le topic, je l'ai posté dans l'espace "Détente", ça n'est pas pour rien, j'ai tout mon temps, c'est pas comme si j'avais un devoir à rendre demain
3: Comprendre ce qui est décrit (même s'il m'arrive de faire des omissions toutes bêtes, je peux compléter ), à savoir:

Citation :
D'abord ça m'étonnerait : la majorité des langages incluent la racine carrée.

alors que j'ai parlé de :
Citation :
c'est simplement que la majorité des langages de programmation que j'ai étudié ne fournissent pas de base la fonction racine
et là, ce que tu as "loupé", c'est le "de base". C'est souvent une bibliothèque annexe qu'il faut appeler et qui ne peut pas traiter les nombre au delà d'un certain seuil. J'avais appris  l'époque des "dinosaures" à le faire à la main, et théoriquement, je devrais pouvoir le refaire, à près tout, ce ne sont que des boucles de tâtonnements . Mais comme je cherche toujours à le faire le plus léger possible, restons-en donc aux fonctions de base (petit rappel l : +-*/ )
4: Mon langage Il y en a qui ont pas froid aux yeux
Citation :
Et si ton langage de miséreux n'a pas de fonction "carré"
Pour rappel, on dit "au carré" . Et je ne vais pas m'arrêter à un langage, le français que je maîtrise pas trop mal il me semble et l'anglais que je devrais reparler un peu, histoire de ne pas trop oublier , et tous les autres que j'ai eu pratiqué depuis ... fort longtemps déjà , mais vu que certains aiment bien cela:
taka aprendralir toikiremont oten d 10no Monsieur LeDino, une bonne nuit , moi je vais casser la gueule a Diablo pour la Xème fois, ça me détendra

Posté par
dpi
re : A propos des nombres premiers 08-06-13 à 10:10

>YgipupCH

J'ai travaillé sur les nombres premiers:

A toutes fins utiles ,je joins les < 1000
triés (sauf 2 et 5 ..)
Je dispose du ficher trié -> 500 000

A propos des nombres premiers

Posté par
ArgShX
re : A propos des nombres premiers 08-06-13 à 12:05

oki, je vois mieux ce que tu veux faire, du coup quelques remarques :

Pour le langage de prog, si tu as du temps devant toi, je te recommande vivement un langage comme Java ou C++. Ces langages sont certes un peu indigestes au départ, mais sur le long terme tu seras gagnant : langage puissant et souple, interfaces de développement dédiées, communauté importante... Après si tu veux rester dans l'efficace mais sans avoir à apprendre une syntaxe compliquée tu peux utiliser des logiciels dédiés aux mathématiques comme Matlab ou Maple (plutôt Maple pour toi d'ailleurs, Matlab c'est plus pour le calcul matriciel numérique). Ces deux là sont payants mais il existe des équivalents gratuits. Bon après Maple ça risque d'inciter à la triche vu que je crois qu'il a une fonction isPrime assez efficace pré-implémentée.

D'un point de vue algorithmique, j'ai l'impression que, après avoir éliminé les multiples de 2 et 5, tu test chaque entier pour voir si il est premier ou non. Si c'est pas ça. Ca c'est pas tip top si ton but c'est de récupérer tous les nombres premiers. En effet, si tu veux tout récupérer, c'est beaucoup plus efficaces d'éliminer tous les multiples de 2, puis tous ceux de 3... c'est à dire appliquer le crible d'Eratosthène.

Enfin, pour l'histoire de la racine carrée, je te conseille quand même de l'implémenter, parce qu'au bout d'un moment calculer des carrés sans arrêt va te coûter bien plus cher que d'évaluer la racine carré. C'est pas parce que ça a l'air plus gentil que ça prend moins de temps de calcul : si l'entier que tu test est 1000000, toi tu vas calculer 1000 mises au carré, moi je calcule une fois une racine carré qui va prendre, disons 10 étapes pour converger, à tout casser. C'est ça l'avantage de la racine ici : c'est a même dans plein de tests, pas la peine d'en calculer plein.

Posté par
carpediem
re : A propos des nombres premiers 08-06-13 à 12:58

salut

je ne sais ce que tu appelles le filtre standard des 60%  mais si on en revient plus ou moins à une méthode de crible on peut tout de même remarquer que la congruence modulo 6 élimine pas mal d'entiers ... (on peut toujours faire mieux en considérant modulo 30 puis 210 puis ....  mais bon faut bien s'arrêter un jour ...)

puisque parmi 6n, 6n + 1, 6n + 2, 6n + 3, 6n + 4 et 6n + 5 seuls 6n + 1 et 6n + 5 ont des chances d'être premier ...

ce qui nous permet de ne tester que deux entiers par "sizaine" ...

à coupler avec la vérification des multiples de 5 .... qui en élimine encore qquns ....

Posté par
carpediem
re : A propos des nombres premiers 08-06-13 à 14:52

ou encore 6n 1 avec n non multiple de 5 a des chances d'être premier ....

Posté par
carpediem
re : A propos des nombres premiers 08-06-13 à 14:53

ha non :: enlever n non multiple de 5 ...

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 17:50

Bonjour tout le monde
Tout d'abord, merci pour vos réponses
Pour ce qui est du fichier, j'ai de quoi faire, j'ai beaucoup travaillé avec un => 50k et j'en ai encore un => + de 42M donc ça jouera
Ci joint, un petit test graphique sur tableur avec ledit fichier => 50k (on finit avec 10.268% de nombre premier )

A propos des nombres premiers

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 18:14

Ensuite, ce filtre des 60%, c'est que, manuellement, en recherche de nombres premiers, il est inutile de vérifier les nombres se terminant par: 2, 4, 5, 6, 8, 0, car automatiquement divisibles . C'est pourquoi, en boucle automatique de 10 en 10 (ça me rappelle un peu le BASIC ) je me contente de vérifier les nombre se terminant par 1, 3, 7, 9 qui et la base même de l'allègement algorithmique. Donc modulo 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, table de référence des 10 premiers "facteurs atomiques" uniquement testé sur les nombres se terminant par 1, 3, 7, 9, par tranches de 10 ... Je ne sais absolument pas si cela peut être démontré mathématiquement parlant, avec ces formules à rallonges où je m'égards dans leur lecture , mais cela me permet déjà de constater que j'allège le modulo de 2 boucles, et les boucles en moins, vers l'infini (les limites du PC, pardon ), je me dits que c'est déjà ça ...
Petit rappel pour la route: tous les nombres dont l'addition des chiffres, quitte à la faire plusieurs fois d'affilé , donne au final un résultat de 3, 6 ou 9 est un multiple de 3 ( et multiple de 9 si c'est 9 ), mais ça, algorithmiquement parlant, c'est fun à programmer, mais plus lourd que modulo 3 .

Posté par
LeDino
re : A propos des nombres premiers 08-06-13 à 18:28

Citation :
Merci à tous de rester courtois et poli sur le forum de façon à ce que le forum reste un lieu convivial et sympathique pour tous, élèves et correcteurs

J'ai été parfaitement courtois, n'ai transgressé aucune règle de politesse et il ne tient qu'à toi que l'échange reste sympathique ...

Posté par
LeDino
re : A propos des nombres premiers 08-06-13 à 18:35

Citation :
c'est simplement que la majorité des langages de programmation que j'ai étudié ne fournissent pas de base la fonction racine...

... et là, ce que tu as "loupé", c'est le "de base".

Je n'ai rien loupé du tout.
Tu parles d'une "majorité" de langages...
Cites-en cinq pour voir ?

En toute cordialité et en toute sympathie ...

NB: et ton tableur là, il ne dispose pas ("de base") de la fonction racine ?

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 18:56

Pour l'allègement par la racine carré, je pense à une boucle de tâtonnement simple, avec les fonctions de base, genre:
Si NP*NP>NAT, arrêt automatique de la boucle, NAT est un nombre premier . Sinon je teste modulo NAT/NP, si 0, arrêt de la boucle, NAT n'est pas un nombre premier , sinon, NP "next" et redémarrage de la boucle "semi-infini", puisqu'il y a 2 occasions d'arrêt   et que le nombre soit premier ou non, le NAT suivant sera testé avec un +2 ou un +4, selon qu'il se termine par 1, 7, 9, ou 3, , ou alors je le réalise en tableau de multiples de 10, récupérant la puissance de 10 comme indice de boucle grande, et son multiple comme indice de boucle interne, avec un + 1, 3, 7 ou 9, selon la position précédente, et +1 à la boucle interne si changement depuis le 9, qui sera automatiquement le 1 . La boucle appelant la fonction booléenne premier or not premier récupère son info, et si oui, par exemple, l'inscrit dans un fichier texte, mais surtout servira de nouveau NP à tester, au fur et à mesure que les recherches avancent
Et là, j'ai tenté de vous résumer les 2 approches de programmations possibles, la première (+2,+4) ayant l'avantage de pouvoir être traitée par le biais de caractères, unité mémoire légère... la deuxième(multiples de puissances de 10), j'ai un peu plus de mal à la mettre en place, elle va plus vite, pas de cast à faire, mais pour la recomposition du nombre, j'ai parfois de la peine, et caster pour concaténer, c'est reperdre le temps gagné précédemment , donc remettre en place la formule à l'envers, galère parfois un peu . Enfin, cela dépend aussi du langage de programmation utilisé ...
Je pense donc utiliser le

Citation :
d'éliminer tous les multiples de 2, puis tous ceux de 3... c'est à dire appliquer le crible d'Eratosthène.
que je dirais filtré du 2 et du 5, puisque mon premier modulo est 3

Posté par
GaBuZoMeu
re : A propos des nombres premiers 08-06-13 à 19:08

Juste une petite remarque : si on travaille avec un grand entier, disons un entier à n chiffres, est-ce qu'une majoration grossière de la racine carrée (du genre 10^{n/2} si n pair) ne vaut pas mieux que de se coltiner le calcul NP*NP à chaque pas ?

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 19:27

Et navré, carpediem, je ne suis pas sûr d'avoir compris le champs d'application de ta formule, car j'ai peur, en l'appliquant comme je l'ai comprise, que je ne loupe des nombres premiers , donc pas sûr de vouloir l'appliquer . Comme je l'ai dit, je suis de la vieille école, et certaines mathématiques me paraissent encore inaccessibles. On ne m'a pas beaucoup enseigné les calculs vectoriels, par exemple, alors que je les utilise dans le cadre de mon travail, de manière instinctive, car l'interfaçage visuel des formules mathématiques sous-jacentes est suffisamment bien fait pour que je n'ai plus vraiment à m'en préoccuper. La machine le fait pour moi . Et le visuel, j'aime beaucoup, surtout avec tout ce que l'on peut faire avec des tableurs, par exemple, un professeur m'a refilé un planisphère programmé sur la base d'une seule date et de la position exacte de chacune des planètes à ladite date. Quand je vois tout ce qu'il existe comme programmes et comme programmations, je me réjouis toujours de voir ce que va donner la "nouvelle génération", même si elle est parfois trop "susceptible", je pense donc m'accrocher encore un peu à Java, après tout, avec le temps, rien n'est vraiment insurmontable, tout en envisageant le C ou le C++ ou le C#, on verra . Merci encore pour vos conseils

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 20:14

Bonjour GaBuZoMeu,
là, navré, c'est de la haute voltige pour moi , et en gros, j'ai encore compris qu'une partie des nombres premiers risquent de ne pas être testés, donc loupés à l'inscription dans la table de référence, qui devient ainsi "caduque", car la table de référence est censé être "valide" en ayant testé tout les nombres qui ont servi à la composer, et ceux qui n'ont pas servi aussi. Une fois qu'un nombre à été validé premier (aucun modulo = 0 avec ses prédécesseur (donc jusqu'à hauteur NP*NP), il est inscrit dans ladite table, et ne représentera un test potentiel que quand un nombre NAT>NP*NP. En revanche, ma première question était justement sur ladite table de référence. Disons que je reprenne l'exemple de celle => 50k , cela veut dire que le dernier nombre premier est 49999 (une "première limite PC" ). Selon la formulation, tout nombre se situant entre 49999 et 99997, se terminant par 1, 3, 7 ou 9, indivisible par chacun des membres de la table de référence (excluant 2&5) jusqu'à hauteur de NP*NP>NAT, est un nombre premier . En reprenant l'exemple de la limite de test, est-ce que le carré augmenterait la "marge de sécurité du test" . Parce que le test, il ne se fait qu'entre 2 variables, dont une s'indexe automatiquement selon la position dudit test, l'autre s'indexe selon la table de référence (un fichier texte en l'occurrence me paraît le type de fichier le plus simple à gérer pour le multi-plateformes, mais pas si simple à boucler en lecture/écriture en langage Java . Encore une fois, je cherche à alléger le code, sans pour autant perdre de sa qualité, parce qu'il deviendrait aussitôt instable car oubli d'un "prédécesseur" et donc dire qu'un nombre est premier alors qu'il ne l'est pas . Et je l'ai fait en tout début de topic, mais personne ne l'a remarqué , tant mieux, parce que je fait quand même la différence entre nombre premiers et ... facteurs atomiques , pour ceux qui aiment la terminologie .

Posté par
GaBuZoMeu
re : A propos des nombres premiers 08-06-13 à 22:00

Désolé, quand il y a trop de smileys, je zappe.

Posté par
ArgShX
re : A propos des nombres premiers 08-06-13 à 22:07

rebonjour,

Bon je vais planter ma tente ici (et continuer à faire de la pub pour Eratosthène et Java)
Quelques remarques en vrac déjà :

Si tu connais les nombres premiers jusqu'à M alors tu peux t'en servir pour vérifier les entiers jusqu'à M^2 (donc largement au-delà de 2M).

Sur le plan programmation il y a quelques trucs auxquels il faut faire attention. Les modulo c'est lourd, ça prend un temps fou à calculer (pour une opération basique bien sûr). Si tu fais beaucoup de calul modulaire dans ton programme, ça va vraiment peser sur les performances. Les lectures/écriture de fichier c'est la MORT . Si tu utilise des fichiers txt, c'est bien mais uniquement pour stocker les résultats, il faut pas avoir besoin d'y accéder pendant l'exécution du calcul.

Du coup, à force d'en parler j'ai fini par coder un ptit truc histoire d'avoir une référence, et ça marche plutôt bien. C'est du crible d'eratosthène basique, en Java (oh yeah). En entrée : jusqu'où on test; en sortie : la liste des premiers jusqu'à cette borne.

Citation :

private static ArrayList<Integer> eratosthene(int max) {
  ArrayList<Integer> primes = new ArrayList<Integer>();
  boolean[] t = new boolean[max];
  t[0] = false;
  for (int i = 1; i < max; i++) {
    t[i] = true;
  }
  for (int i = 0; i < max; i++) {
    if (t[i]) {
      primes.add(i + 1);
      for (int j = 2 * (i + 1); j < max + 1; j += (i + 1)) {
        t[j - 1] = false;
      }
    }
  }
return primes;
}


Et donc pas besoin de racine, ni de carré, ni de modulo, ni de multiplication d'ailleurs.

Il me renvoie les premiers jusqu'à 179.424.673(le dix millionième nombre premier) en 7.5 secondes. Il crash (manque de mémoire) joyeusement quand j'essaye avec 1 milliard. En même temps c'est normal, j'utilise justement beaucoup de mémoire pour gagner du temps...

Posté par
YgipupCH
re : A propos des nombres premiers 08-06-13 à 22:31

Désolé GaBuZoMeu, c'est juste que, étant dans l'espace détente, je m'amuse un peu, comme je peux le faire avec les nombres premiers, par exemple.

Merci ArgShx, là je suis sur un poste où je n'ai pas encore installé de GUI ( à part peut-être des jeux, mais ça demande peut-être trop de contraction de l'esprit pour certains...). Je me réjouis néanmoins de tester ces quelques lignes dès Lundi. Et crois-moi que j'adore faire mes test en moyenne et extrêmes raisons, donc le passer au crible de mes mauvaises & bonnes habitudes aussi, surtout si je peux corriger mes mauvaises habitudes

Sur ce, bonne soirée, je me réjouis de voir ce que je vais découvrir demain

Posté par
carpediem
re : A propos des nombres premiers 09-06-13 à 16:43

je disais simplement qu'un nombre qui n'est pas de la forme 6n + 1 ou 6n + 5 n'est pas premier ... ce qui permet d'en éliminer plus que seulement les nombres pairs

et si en plus n est multiple de 5 alors on peut éliminer aussi 6n + 5 ...


ArgShX ::

pourrais-tu m'expliquer un peu ton programme ::

en numérotant toutes les lignes (même les }) ::

1 :: demande M et créer un tableau de longueur M  (pourquoi private ? static ?)
2 :: crée le tableau des premiers (de façon dynamique :: il se complète au fur et à mesure ??)
3 :: ??  et pourquoi "new" ?

la première boucle semble créer un tableau booléen à vrai sauf t[0] ... et pourquoi pas t[1] aussi ?

deuxième boucle ::

10 :: ??  ajoute i + 1 comme nouveau premier ??
11 :: ?? (boucle j)


merci par avance

Posté par
ArgShX
re : A propos des nombres premiers 09-06-13 à 18:45

Bon, je vais essayer d'expliquer mon code sans trop rentrer dans la  syntaxe de Java.

Citation :
private static ArrayList<Integer> eratosthene(int max)

déclaration d'une méthode (eratosthene) qui prend en argument un entier (max) et qui renvoie une liste d'entier. private et static ne nous intéressent pas ici et n'on aucun effet algorithmique. ArrayList c'est la structure Java la plus souvent utilisée pour manipuler des listes.

Citation :
ArrayList<Integer> primes = new ArrayList<Integer>();

Création de la liste qui sera utilisée pour renvoyer le résultat (primes).

Citation :

boolean[] t = new boolean[max];
t[0] = false;
for (int i = 1; i < max; i++) {
  t[i] = true;
}

Création d'un tableau de booléen de longueur max. L'idée c'est que la case i représente l'entier i, et t[i] est à faux si i a été éliminé par le crible. Au début tout est à vrai, sauf la case 1 (d'indice 0).

Citation :
for (int i = 0; i < max; i++)

On boucle sur tous les entiers jusqu'à max

Citation :

if (t[i]) {
  primes.add(i + 1);
  ...
}

Si quand on arrive à i t[i] vaut vrai alors i+1 est premier, on l'ajoute à la liste. Sinon on avance dans la boucle. Le +1 vient juste du fait que la case 1 c'est t[0], c'est de l'ajustement, rien d'important. L'idée c'est que lorsqu'on trouve un nombde premier p, on passe toutes les case multiples de p à faux, donc si la case i est à vrai, c'est que i n'est multiple d'aucun nombre premier, donc qu'il est premier.

Citation :

for (int j = 2 * (i + 1); j < max + 1; j += (i + 1)) {
  t[j - 1] = false;
}

Cette boucle passe à faux toutes les cases d'indice multiple de i+1, à partir de 2(i+1) jusqu'à max+1. Les +1/-1 c'est encore de la bidouille sur les indices, à la relecture j'ai pas fait les choix les plus lisibles, mais ça reste très compréhensible.


Pour résumer, et se détacher un peu du code, voilà ce que ça fait : je prends tous les entiers jusqu'à une certaine limite. Je barre 1, qui n'est pas premier. Je regarde le plus petit qui n'est pas barré, c'est 2. 2 est premier, je barre tous ses multiples. Et je continue : le plus petit pas barré est premier, je barre tous ses multiples etc...

Posté par
carpediem
re : A propos des nombres premiers 09-06-13 à 20:02

ha oui ok ... merci très beaucoup beaucoup ...

j'ai immédiatement compris dès que j'ai saisi ce décalage d'indice qui m'a perturbé et ensuite évidemment cette boucle "j" ...

encore une fois un très grand merci ...


juste une dernière question :: on peut traiter de "grands" entiers ?

va falloir que je m'y mette sérieusement .... avec ces "nouveaux" langages .... dont la syntaxe est parfois déroutante ... comme l'incrémentation ...

Posté par
carpediem
re : A propos des nombres premiers 09-06-13 à 20:02

et je trouve que c'est effectivement très puissant ... en terme de temps ....

Posté par
carpediem
re : A propos des nombres premiers 09-06-13 à 20:05

dont la syntaxe est parfois déroutante ... comme l'incrémentation ...  ou l'ajout d'un élément à une liste ...

Posté par
YgipupCH
re : A propos des nombres premiers 10-06-13 à 09:21

Bonjour tout le monde

Juste pour info, carpediem, Java traite les:
int: de -2147483648 à 2147483647
long: de -9223372036854775808 à 9223372036854775807
et après, il te faut songer à BigInteger, qui semble ne pas avoir de limite, à part la mémoire du PC...
Et je songe déjà à travailler avec les BigInteger, vu que je parle en limites du PC

Posté par
YgipupCH
re : A propos des nombres premiers 10-06-13 à 09:52

Et merci encore ArgShx, c'est très sympathique comme lignes de commandes, mais:
ArrayList pour contenir les nombres premiers, j'y avais songé, j'y ai travaillé, mais vu ce que cela bouffe comme mémoire, j'ai laissé de côté cette idée. Je lui préfère une table "allégée" des 10 premiers facteurs atomiques pour la rapidité d'accès, vu que, par exemple, 3 élimine 33.3% des nombres (très fréquent), alors que 37 n'élimine que 2.7% des nombres (moins fréquent), ensuite, si je sors de cette table, je passe en lecture de fichier, stocké provisoirement dans une variable, et comparé à une variable type boucle. Ce qu'il en résulte, c'est que la place mémoire n'est encombrée que de la table de base, du code (qui d'ailleurs contient ladite table ), et 2 variables genre BigInteger à comparer. La limite de la table est alors le fichier texte en lui même (pourquoi pas 1Tb, par exemple, mais en gestion de fichier, je ne suis pas encore au point ). Encore une fois, je ne suis pas pressé, donc je ne cherche pas à le faire "au plus vite", mais "au plus juste" & "au plus complet", tout en allégeant le code au minimum (on pourrait croire que je cherche à programmer un virus ).

Posté par
ArgShX
re : A propos des nombres premiers 10-06-13 à 11:10

En fait l'utilisation d'ArrayList n'est pas du tout limitante dans mon code, c'est le tableau t qui va poser problème en premier (ce qui est logique). ArrayList n'est ici qu'un moyen de renvoyer le résultat, je ne fais jamais de lecture de cette liste. Par ailleurs il est bon de signaler que cette structure est très optimisée (très beaucoup beaucoup, comme dirait l'autre ).

Pour ce qui est de l'utilisation de la mémoire, quelques rappels. De nos jours avoir beaucoup de mémoire est très facile, alors qu'augmenter le nombre d'opérations par secondes est de plus en plus complexe. Utiliser au maximum la mémoire pour décharger le processeur est naturel et c'est une bonne pratique. Par ailleurs utiliser un fichier annexe ne résoudra a priori pas le problème, vu que le fichier est chargé dans la mémoire dès que tu veux le lire.

Pour ce qui est de la limite sur les entiers, soit tu as sous la main un procédé révolutionnaire, soit il va falloir y aller un peu plus doucement. Mon code, que j'estime efficace en temps, calcule les nombres premiers jusqu'à 500 millions en 30 secondes environ. Sur cette base, il faudrait pas loin de 2000 ans pour aller jusqu'à la valeur maximum d'un entier 64 bits (long), je parle même pas d'un BigInteger. Et j'ai fais le calcul comme si mon algorithme était linéaire (temps de calcul proportionnel à l'entrée), ce qui n'est absolument pas le cas, il est quadratique.

Sinon, est-ce que tu as pu exécuter mon code ? Par rapport à ce que tu as fait, ça donne quoi ?

Posté par
YgipupCH
re : A propos des nombres premiers 10-06-13 à 14:06

Bonjour ArgShx

J'ai beaucoup aimé jouer avec ces lignes de code

Par rapport à ce que j'ai fait, cela donne une chouette approche, mais que je dirais "opposée" à ma manière de penser, car principalement, issu de la vieille école où 1Ko c'était beaucoup , je ne cherche absolument pas à avoir beaucoup de processus qui tournent en même temps (quoique, par évolution, on peut envisager le même processus tournant sur différents nombres ). Ma recherche va plutôt vers une utilisation des diverses ressources, selon leurs possibilités & capacités, afin de ne traiter en mémoire que le processus sur 2 variables (surtout si lesdites variables sont des grands nombres). Dommage que Java, comme il me semblait et que tu sembles confirmer, ne puisse lire "partiellement" avec un indexage un fichier texte . Vu cela, je vais plutôt approfondir mes connaissances en Ada ... Je ne sais pas si celui là le permettra, mais après tout, je suis encore en phase recherches et développements, j'ai du temps devant moi (c'est un travail perso redondant )
Et malheureusement, je suis rapidement arrivé à une limite du programme liée au PC. Ayant probablement un plus petit PC, je n'ai déjà pu calculer que jusqu'à 30M sans plantage PC (plus haut, il plante mon GUI en boucle infini ), alors que int va déjà à + de 2T (limite non franchie ) et je ne te parle même d'envisager le même traitement sur les long (+ de 9Z ), voir les BigInteger
Mais cela me laisse une excellente base de travail, que je peux aisément envisager d'utiliser dans certaines de mes recherches, donc merci encore ArgShx

Posté par
carpediem
re : A propos des nombres premiers 10-06-13 à 16:26

merci à tous les deux ...

Posté par
YgipupCH
re : A propos des nombres premiers 11-06-13 à 11:43

Bonjour tout le monde
De rien carpediem
En revanche, j'ai fait une étude "rapide" de la "sizaine" afin de voir son intérêt dans l'implémentation de mon code. Comme je pense que je n'ai pas bien compris son champ d'application, voici ce que, visuellement parlant, j'obtiens comme résultats:

 Cliquez pour afficher


Premier champ de traitement, les nombre premiers déjà connus. Le constat est vite fait, il me manque des nombres premiers après traitement.

2ème champ de traitement, tous les nombres, ce que je ne fais pas normalement. Ca joue, mais j'ai l'impression que je n'y gagnerai pas grand chose.

3ème champ de traitement, les nombres se terminant par 1 3 7 ou 9, et là, je pense que rajouter un bouclage à mes bouclages actuels ne ferait qu'alourdir mon code, sans aucun gain et même plus de perte qu'avec les nombres premiers uniquement.

Ai-je omis quelque chose dans la formulation ou son application? A partir de quand dois-je changer mon modulo 6 en 30 ou 210?

Je suis d'accord de rajouter des bouclages à mon code, mais s'il cela me fait perdre en qualité, je ne préfère pas

Posté par
carpediem
re : A propos des nombres premiers 11-06-13 à 16:55

ArgShx nous montre qu'avec les outils puissants actuellement à disposition le crible est probablement le plus efficace ....

ce que je te faisais remarquer c'est que plutôt que de regarder tous les nombres se terminant par 1, 3, 7 ou 9 il est préférable (une autre idée) de ne regarder que les nombres de la forme 6n + 1 ou 6n + 5 car tout premier est de cette forme (donc 2 cas par sizaine au lieu de 4 cas par dizaine).... (au delà de 5 bien sur) .. mais la réciproque est évidemment fausse ...

maintenant on peut encore remarquer que :

si n est multiple de 5 alors 6n + 5 aussi (un test permet d'éliminer ce cas)

si n est multiple de 5 - 1 (n = 5k - 1) alors 6n + 1 est multiple de 5 (un test permet d'éliminer ce cas)

ce qui il me semble évitera bon nombre de boucles et permet de gagner du temps ....

en fait j'étudie la congruence modulo 6 et donc 2 possibilités qui couplé avec les deux tests t'élimine les multiples de 5 ...

maintenant on peut regarder modulo 30 qui élimine les mutiples de 2, 3 et 5 mais oblige peut-être à regarder trop de cas (à voir les restes) ....

Posté par
YgipupCH
re : A propos des nombres premiers 19-06-13 à 12:00

Bonjour à toutes et à tous et désolé pour ce silence, je faisais des tests, dont voici le résultat:

 Cliquez pour afficher

12 lignes de code, ça devrait pas être trop indigeste (et j'aurais pu les réduire à 9, si je n'avais pas du faire ces 4 commentaires )
Merci encore à ArgShx et carpediem , vous saurez peut-être reconnaître votre contribution dans ces lignes.
Ces lignes sont fonctionnelles (ctrl+c, ctrl+v, corriger certains noms & lancer), même si elles risquent de planter votre PC de diverses manières
Bon, je vais pas être trop vache, voici le visuel de ma progammation, mais il y a des commentaires et des smiley, tant pis pour ceux qui les zap
 Cliquez pour afficher

Maintenant, pour ceux qui ont encore envie de me lire , voici d'autres lignes, d'autres fonctions, et surtout plein, mais alors plein plein plein de commentaires, de smiley, et un autre type de sortie
Avant de vous lancer dans cette lecture, pensez que j'ai rédigé ces lignes pour tout néophyte en Java
 Cliquez pour afficher

Amusez-vous donc avec ces lignes, surtout les balises, ça aide à comprendre la quadratique du temps
Malheureusement pour carpediem, ta contribution tombe à l'eau, trio() a rendu sa balise inactive. Remarque, je ne l'avais peut-être pas mise au bon endroit
Sachez encore que ces lignes ne sont que le cœur de ma programmation, il y a plein de manière d'agir avec ces 3 paramètres essentiels que sont tfa, fat & fitr. Et ma différence de programmation essentielle d'avec toi, ArgShx, est que je ne compte pas les nombres non premier (~90%=>50k) et les premiers (~10%=>50k), mais uniquement les premiers, qui comme toi seront inscrits dans la tfa. Se balader vers l'infini avec quelque chose d'inutile, c'est comme courir un 100m avec un boulet au pied. Le mien de boulet, du coup, c'est la réinitialisation de fitr, encore et encore, pour aller chercher tous les diviseurs dans ma tfa jusqu'aux carrés dépassants ou égaux . Mais sachant où est le boulet, je travaille dessus Et j'espère récupérer l'info des carrés pour me faciliter les traitements, mais pas facile, en quadratique, de savoir dans quel sens je vais & une erreur quadratique dans une erreur quadratique, ça fait vite beaucoup
Et une autre trouvaille dans mes vieux travaux:
-\infty 1 \infty 0 \infty 1 \infty
Si quelqu'un y voit là un développement quelconque de programme, je suis preneur Je n'ai qu'une remarque à son sujet: condensé

Posté par
ArgShX
re : A propos des nombres premiers 20-06-13 à 14:17

Rebonjour,

Ne le prend pas mal, mais ton code est immonde . Je vais essayer de passer en revue ce qui ne va pas au niveau du code (le premier) et du point de vue algorithmique.

Déjà, indente ton code, ce sera plus lisible. C'est sûr que là t'as 12 lignes mais personne ne peut les lire. Sous quel système tu code ? Dans tous les cas Eclipse est disponible, tu devrais essayer, il te permet d'auto-indenter le code (ctrl+shift+F), et je suis sûr que plein d'autres interfaces proposent cette fonctionnalité. On passe tout de suite à 100 lignes.
Ensuite ton utilisation des méthodes est... particulière : tu passe pas d'argument et tu n'en récupère pas, tu fais que jump vers un endroit du code et provoquer des effets de bord via les variables statiques. C'est peu élégant, peu efficace est très peu lisible.
Tu as aussi des trucs très étranges, du genre :

Citation :

if (premier == true) {
  tfa.add(fat);
  premier = false;
  appel();
} else {
  if (premier == false) {
    appel();
  }
}

si tu es passé dans le else, je vois pas trop pourquoi retester premier==false... De même, appel() n'est jamais qu'un test pour voir si on sort de la boucle alors pourquoi ne pas le mettre directement dans le test du while, plutôt que de stocker la valeur et l'utiliser ensuite. Un autre truc :
Citation :

fat - (fat / 10) * 10

tu le fait pour récupérer le dernier chiffre de fat en base 10, mais ça ça s'écrit fat % 10. C'est l'exemple typique de ce qui ne va pas dans le code : tu fais des trucs inutilement alambiqués, ça perturbe vraiment la compréhension du truc. Bref, le code est correct, mais il y a moyen de violement le simplifier, sans rentrer du tout dans l'algorithmique.

Maintenant sur un plan plus général, je ne comprend toujours pas pourquoi tu refuses d'utiliser de la mémoire (enfin, de toute façon tu en utilises plein pour stocker le résultat) : quelle est la motivation de ce choix ? Surtout, est-ce un challenge que tu te fixe (dans ce cas là ok) ou penses-tu que tu sera moins limité si tu fais ce choix (dans ce cas c'est faux).
Juste pour fixer les idées, j'ai refais quelques tests. J'ai fait un ptit graphe du temps de calcul (cf. image ci-dessous) en utilisant le code que j'ai déjà montré(rouge), une version personelle qui n'utilise pas plus de mémoire que la tienne(vert) et ton code(bleu). L'axe x est en échelle logarithmique, sinon on voit pas grand chose. Ce que ça veut dire en bref, c'est que vu le temps d'exécution de ton code (courbe bleue), c'est bien le temps qui te limite et pas la mémoire. Sauf si tu as quelques milliers d'années devant toi, mais je crains que la machine n'y survive pas.

A tout hasard, voici le code utilisé pour la courbe verte :
 Cliquez pour afficher


Tout ça pour dire qu'une idée simple bien implémentée c'est souvent plus efficace qu'une usine à gaz, et en tout cas c'est bien de commencer par là pour avoir une référence.

A propos des nombres premiers

Posté par
YgipupCH
re : A propos des nombres premiers 20-06-13 à 15:55

Re ArgShx,
Ne le prend pas mal , mais je sais que mon code est immonde, c'est pour les pressés qui n'ont pas envie de lire: copier, coller, et comme tu l'as si bien dit: ctrl+shift+F. Je l'ai aussi, mais là c'est plus pour faire réagir ceux qui ne commentent jamais, qui sont bien souvent aussi ceux qui ne lisent jamais
Ensuite, si tu n'as travaillé qu'avec la version non commentée, je comprends très bien tes remarques. Même dans la version commentée j'ai encore plein d'erreur à corriger, du code à rajouter, ...
Merci pour les 2 corrections que tu m'as apporté, c'est vrai qu'à force de faire des choses comme j'en avais l'habitude j'en oublie certaines fonctionnalités
Si ce langage n'était pas aussi susceptible et me lâchait la grappe avec des détails que le GUI pourrait aisément corriger tout seul je pourrais me concentrer un peu plus sur la fonctionnalité du code ...
D'ailleurs, depuis hier, j'ai implémenté une nouvelle méthode (qui était ébauchée dans la version commentée ). J'ai drastiquement réduit mes temps de calcul, mais désormais je n'atteins plus que 200M avant un plantage mémoire, alors que mes lignes non commentée (légèrement modifiée: on ne peut pas afficher dans la console des millions de nombres ) m'ont permit de grimper mes test => 2T (plus de 7h de calcul ) . Et je résumerais ma façon de programmer ainsi: 50M de booléen => 47.68Mo et 2T => 1.86 Go
Ca grimpe plus vite que ma tfa que je cherche toujours à faire dans un fichier texte
Quand à ces nouvelles lignes, je ne sais comment les livrer: commentées ou non (boolean )
De plus je travaille encore sur tes lignes, qui ne sont pas directement fonctionnelle, contrairement aux miennes
Cordialement

Posté par
ArgShX
re : A propos des nombres premiers 20-06-13 à 20:01

Je proteste, mon code est parfaitement fonctionnel ! Si le problème c'est que c'est pas dans une classe... voici une version un poil plus complète, mais vraiment ça change rien :

 Cliquez pour afficher


Voilà, il y a mes 2 méthodes avec quelques simplifications syntaxiques et ça s'exécute direct.

Sinon, tu parles de 2T : pour moi T c'est 10^{12}, si vraiment t'as été jusque là en 7h, ça relève de la magie. Vu les résultats de mes tests, ce serait plutôt 2G (2 milliards) non ? Ce serait déjà une belle performance en tout cas !

Sinon pour les lectures de fichier je pourrait ptet faire un truc, mais normalement avec BufferedReader et BufferedWriter on arrive à faire ce qu'on veut sans trop de problèmes.

Posté par
YgipupCH
re : A propos des nombres premiers 21-06-13 à 09:16

Bonjour à toutes et à tous
Salut ArgShx
1: Je n'ai jamais dit que ton code n'était pas fonctionnel, juste qu'il faut écrire son propre main, faire ses déclaration de variables, ... bref: tout ce qu'un néophyte sait faire comme ça, bien sûr
2: Merci pour la version plus complète, je m'y mets de ce pas ...
3: Je n'ai plus les résultats du 2T, mais c'était pour atteindre la limite de int (2147483647) et je n'ai aucune idée du temps passé à calculer vu que le message d'erreur a coupé les boucles et résultats
4: Voici un résultat atteint en plus de 7h (pas de beaucoup )

 Cliquez pour afficher

Et celui là, je ne suis même plus sûr que je l'ai fait calculer avec ma nouvelle méthode, mais vu la limite (200G ), je suppose que oui.
J'ai tellement de résultats possibles, tellement de lignes de codes en bouts d'essais, bref, c'est vite le foutoir, et quand je reprends mes vieux travaux, qui sont dans le même état , j'ai parfois du mal à poser les formules au bon endroit. Résultat, je pense savoir où je vais pouvoir utiliser n=>2n, mais il va falloir encore que je test
Et je précise encore (et encore!): la mémoire, on en a jamais assez ! ! !
Cordialement
PS: Je me réjouis d'avance de voir ce que tu vas proposer pour la lecture de fichier, mais n'oublie pas un truc fondamental: lectures et écritures avec indexages et compilation de plusieurs fichiers "indexés" vers un fichier final
PPS: 2=11 & 3=10, et tu me parles d'effets de bords J'aimerais vraiment comprendre où, quand, comment, quel outil de mesure, bref, que peux-tu me dire de plus à ce sujet
PPPS: Je travaille avec les GHz & les Go avec ma mémoire (enfin, j'essaie ). D'après mes notes, c'est ce que l'on appelait "travailler en 2 dimensions". Suis-je donc tellement "dinosaure" que ça a finit par disparaître

Posté par
YgipupCH
re : A propos des nombres premiers 21-06-13 à 14:57

Petite correction, après vérifications, je n'avais pas fait ce test avec ma nouvelle méthode
Voici ses résultats:

 Cliquez pour afficher

Je crois que cela valait le coup de rajouter ma méthode Plus vite, mais pas vraiment plus loin, parce que au dessus, ça plante, alors que l'ancien test est probablement un résultat intermédiaire lancé un soir avant de partir de mon poste



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !