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:
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
Bonjour,
Entre n et 2n, il existe toujours un nombre premier.
C'est un théorème de Bertrand, démontré par Tchebychev.
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).
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...
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. est largement supérieur à . Donc oui ça marche en faisant les calculs jusqu'à , mais c'est une perte de temps monumentale.
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 et , je vais de ce pas réviser ma programmation
Merci encore
Bonjour,
Dans mes souvenirs, une manière "simple" et efficace pour extraire la racine d'un nombre et considérer la suite
Jusqu'à ce que , où est une tolérance de calcul donnée. J'utilise d'habitude mais c'est à toi de voir ce dont tu as besoin.
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
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
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).
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
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...
@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 ...
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:
>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
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.
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 ....
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 )
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 .
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
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 si n pair) ne vaut pas mieux que de se coltiner le calcul NP*NP à chaque pas ?
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
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 .
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'à alors tu peux t'en servir pour vérifier les entiers jusqu'à (donc largement au-delà de ).
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.
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
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
Bon, je vais essayer d'expliquer mon code sans trop rentrer dans la syntaxe de Java.
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 ...
dont la syntaxe est parfois déroutante ... comme l'incrémentation ... ou l'ajout d'un élément à une liste ...
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
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 ).
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 ?
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
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:
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) ....
Bonjour à toutes et à tous et désolé pour ce silence, je faisais des tests, dont voici le résultat:
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 :
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
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 :
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 )
Petite correction, après vérifications, je n'avais pas fait ce test avec ma nouvelle méthode
Voici ses résultats:
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :