380 qui est le prochain multiple de 19 après 361 n'est pas dans la liste.Envoyé par iharmed
Pour cause, puisque 380 est enlevé précédemment selon un premier critère (nombre pair pour commencer).
Ce qui fait évidemment que la répartition des multiples de 19 dans la liste "écrémée" ne sera pas "uniforme" (entendu, il existe un écart de 19 entre ces multiples).
JE SAIS POUR 3, 5 ET 7 QUE OUI.
j'explique pour 7
les nombres restants après suppression des multiples de 2, 3 et 5 sont :
49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 151 157 161 163.
les multiples de 7 sont en rouge. la répartition est claire on saute 6 nombres puis on saute 3, puis 6 puis 3 puis 6
On est très content de le savoir mais j'ai demandé pour 11, 13, et 17...
Parce comme déjà dit il y a pas mal de messages, le problème commence avant 19. Et franchement, on a parfois l'impression que tu redécouvres la roue mais que la tienne est carrée et que tu viens nous expliquer que comme ça elle freine mieux (citation de Dilbert, l'humour étant la politesse du désespoir).
il faut que je calcul pour 11.
je revient au 7
j'ai donné les premiers nombre jusqu’à 163, c'est uniforme par bloc de 2 (6 et 3)
mais si je donne plus et je rajoute
161 163 167 169 173 179 181 187 191 193 197 199 203 209 211 217 221 223 227 229 233 239 241 247 251 253 257 259 263 269 271 277 281 283 287 289 293 299 301 307 311
je le vois que la répétition change : 6, 3, 6, 3, 6, 11, 2, 11 et cette fois c'est définitive est la répartition des multiples de 7 est faite par bloc de 8.
pour le 19 il y a une répartition uniforme mais par bloc consistant (je conjecture)
j'ai vérifier pour 11
après suppression des multiples de 2, 3, 5 et 7. dans l’ensemble restant, les multiples de 11 sont répartis uniformément par bloc de 48 éléments : on saute 4, puis on saute 9 puis 4 puis ... jusqu'au dernier (le 48eme) on saute 25 et on reprend -- (4, 9, 4, 10, 14, 3, 15, 9, 4, 8, 14, 15, 4, 14, 9, 4, 14, 10, 13, 19, 10, 4, 8, 4, 10, 19, 13, 10, 14, 4, 9, 14, 4, 15, 14, 8, 4, 9, 15, 3, 14, 10, 4, 9, 4, 25, 2, 25).
voici les éléments restant après suppression des multiples de 2, 3, 5 et 7. à vous de vérifier :
121 127 131 137 139 143 149 151 157 163 167 169 173 179 181 187 191 193 197 199 209 211 221 223 227 229 233 239 241 247 251 253 257 263 269 271 277 281 283 289 293 299 307 311 313 317 319 323 331 337 341 347 349 353 359 361 367 373 377 379 383 389 391 397 401 403 407 409 419 421 431 433 437 439 443 449 451 457 461 463 467 473 479 481 487 491 493 499 503 509 517 521 523 527 529 533 541 547 551 557 559 563 569 571 577 583 587 589 593 599 601 607 611 613 617 619 629 631 641 643 647 649 653 659 661 667 671 673 677 683 689 691 697 701 703 709 713 719 727 731 733 737 739 743 751 757 761 767 769 773 779 781 787 793 797 799 803 809 811 817 821 823 827 829 839 841 851 853 857 859 863 869 871 877 881 883 887 893 899 901 907 911 913 919 923 929 937 941 943 947 949 953 961 967 971 977 979 983 989 991 997 1003 1007 1009 1013 1019 1021 1027 1031 1033 1037 1039 1049 1051 1061 1063 1067 1069 1073 1079 1081 1087 1091 1093 1097 1103 1109 1111 1117 1121 1123 1129 1133 1139 1147 1151 1153 1157 1159 1163 1171 1177 1181 1187 1189 1193 1199 1201 1207 1213 1217 1219 1223 1229 1231 1237 1241 1243 1247 1249 1259 1261 1271 1273 1277 1279 1283 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1331 1333 1339 1343 1349 1357 1361 1363 1367 1369 1373 1381 1387 1391 1397 1399 1403 1409 1411 1417 1423 1427 1429 1433 1439 1441 1447 1451 1453 1457 1459 1469 1471 1481 1483 1487 1489 1493 1499 1501 1507 1511 1513 1517 1523 1529 1531 1537 1541 1543 1549 1553 1559 1567 1571 1573 1577 1579 1583 1591 1597 1601 1607 1609 1613 1619 1621 1627 1633 1637 1639 1643 1649 1651 1657 1661 1663 1667 1669 1679 1681 1691 1693 1697 1699 1703 1709 1711 1717 1721 1723 1727 1733 1739 1741 1747 1751 1753 1759 1763 1769 1777 1781 1783 1787 1789 1793 1801 1807 1811 1817 1819 1823 1829 1831 1837 1843 1847 1849 1853 1859 1861 1867 1871 1873 1877 1879 1889 1891 1901 1903 1907 1909 1913 1919 1921 1927 1931 1933 1937 1943 1949 1951 1957 1961 1963 1969 1973 1979 1987 1991 1993 1997 1999 2003 2011 2017 2021 2027 2029 2033 2039 2041 2047 2053 2057 2059 2063 2069 2071 2077 2081 2083 2087 2089 2099 2101 2111 2113 2117 2119 2123 2129 2131 2137 2141 2143 2147 2153 2159 2161 2167 2171 2173 2179 2183 2189 2197 2201 2203 2207 2209 2213 2221 2227 2231 2237 2239 2243 2249 2251 2257 2263 2267 2269 2273 2279 2281 2287 2291 2293 2297 2299 2309 2311 2321 2323 2327 2329 2333 2339 2341 2347 2351 2353 2357 2363 2369 2371 2377 2381 2383 2389 2393 2399 2407 2411 2413 2417 2419 2423 2431 2437 2441 2447 2449 2453 2459 2461 2467 2473 2477 2479 2483 2489 2491 2497 2501 2503 2507 2509 2519 2521 2531 2533 2537 2539 2543 2549 2551 2557 2561 2563 2567 2573 2579 2581 2587 2591 2593 2599 2603 2609 2617 2621 2623 2627 2629 2633 2641 2647 2651 2657 2659 2663 2669 2671 2677 2683 2687 2689 2693 2699 2701 2707 2711 2713 2717 2719 2729 2731 2741 2743 2747 2749 2753 2759 2761 2767 2771 2773 2777 2783 2789 2791 2797 2801 2803 2809 2813
Et les blocs vont devenir de plus en plus long... Le prochain est à 480 et celui du 19 doit être au dela du million.
Ce qui rend l'algo non praticable.
Salut,
J'ai pas tout suivi là. Ce n'est plus Ératosthène ? Qu'est-ce qui m'a échappé ???
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Si, c'est toujours Ératosthène.
Mais l'idée est de travailler sur des "blocs" toujours plus petit. En gros, tu vires les multiples de 2 et tu transmets les impairs à une autre machine.
Elle vire les multiples de 3 ce qui est facile : on a une période.
Et tu transmets les impairs non multiples de 3.
Et tu vires les multiples de 5.
C'est en gros et si j'ai bien compris l'algo qu'il a proposé dès le début pour faire du crible sans exploser la mémoire.
Sauf qu'il avait raté qu'on ne fait pas de la chimie et que ce n'est pas parce que ça marche pour 2 et 3 que ça marche toujours (et je ne parle même pas des problèmes informatiques).
Effectivement, pour que ça marche il ne suffit pas de vérifier que ça marche (ce qui est d'ailleurs une tâche infinie), il faut le démontrer, on est en math, pas en science de l'observation.
D'accord, j'ai compris.
En fait dans la parallélisation, j'avais autre chose en tête, pas cent pour cent optimal mais qui améliore quand même le traitement monoprocesseur.
Une machine élimine les multiples de 2, une autre élimine les multiples de 3, etc....
La seule chose qu'il faut gérer est l'accès à une mémoire commune (ou une "fusion" finale).
Pour info, tout à l'heure j'ai été voir les méthodes de génération proposées sur le net. Et je n'en vois effectivement que trois :
- Eratosthène (amélioré par divers trucs informatiques)
- balayage et tests de primarité (éventuellement en éliminant automatiquement certains multiples, j'avais déjà programmé ça, c'est facile et rapide)
- fonction mathématique donnant les premiers : ok sur papier, irréalisable en pratique. Voir les fonctions données dans wikipedia. Celui qui trouvera une formule mathématique efficace sera célèbre
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Donc tu situerais le Crible d'Atkin dans la seconde catégorie ?
il me semble que ce n'est pas tout à fait cela ( dans ton intitulé :"balayage et test de primalité" )
Non, dans le premier, c'est une amélioration d'Eratosthène (pas entièrement informatique, il est vrai, ça utilise une propriété mathématique)
Pour moi c'est "crible" ou "test primarité". Je ne vois pas autre chose.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ben en fait, il me semblait qu'il associait les deux, justement.
Cdt
En effet. On peut mixer. Et je suppose qu'on peut faire encore mieux
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Bon
C’est un travail à faire par les machines sans les saturer.
A chaque itération la machine est vierge et travail sur une nouvelle liste qui est débarrassée de pas mal de multiples de nombre premier ou il y a plus de premier que de non premier.
En plus, dans une itération, la machine n’a que la tâche d’écraser les multiples d’un nombre premier et transmettre puis effacer les nombres restants à une autre machine, elle renouvelle ainsi son énergie et peux continuer indéfiniment.
Yakafokon...
C'est tellement faux et cela ne veut tellement rien dire que c'en est presque rigolo.
Ok , J’ai compris que je ne serai pas compris.
La logique utilisée m’échappe
Une proposition est fausse et elle ne veut rien dire. D’après la logique que j’utilise, s’est absurde, elle ne veut rien dire ça signifie qu’elle est peut être fausse ou peut être vrai.
Ca me dépasse tout cela, il faut que je me réinitialise
Salut,
Lorsqu'elle ne veut rien dire, il est assez difficile de dire si elle est fausse
C'est la règle numéro un. Si ça ne marche pas : couper et allumer. Ensuite aller dans les bureaux des collègues : "dites, vous avez le même problème ?". Et enfin, appeler le HelpDesk.
Et dernier recours, jeter l'ordi par la fenêtre mais j'ai remarqué que certains employeurs n'apprécient pas
Et puis il y a les pannes des blondes, ça c'est les pires :
Lu dans un bêtisier :
"Une utilisatrice m'appelle un jour et me dit qu'elle a changé son Mac de bureau, et que depuis ce jour, il ne veut plus redémarrer. Je lui pose les questions rituelles, est-il branché, est-il allumé, les cables sont-ils tous connectés, etc... et elle répond "oui" à toutes mes questions. Je me rends à son bureau, et je suis tous les cordons à travers un fouillis de cables jusqu'à la multiprise.
Elle avait juste branché le cordon d'alimentation de la multiprise SUR la multiprise...!"
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Déjà vu également.
@Iharmed : je te conseille de séparer dans ton discours les deux choses différentes:
- l'algorithme,
- la mise en œuvre, avec les ordinateurs etc.
Le deuxième point, la mise en œuvre, concerne notamment (mais pas seulement) le traitement parallèle par plusieurs processeurs, et pourrait être appliqué à tout autre chose que la recherche des nombres premiers. Et donc tu passes beaucoup de temps à expliquer ce point alors qu'il est , on va dire hors sujet, ou qu'il pourrait être traité dans une autre discussion.
Et quant au premier point, l'algorithme, eh bien si tu l'extrais de ton discours, lui tout seul, tu verras, comme nous te l'avons déjà fait remarquer, que ce n'est rien d'autre que l'algorithme de Eratosthène. Fais cet effort de séparation entre ces deux parties de ton discours et tu t'en rendras compte.
C'est justement ce que voulait faire remarquer Iharmed.Lorsqu'elle ne veut rien dire, il est assez difficile de dire si elle est fausse
Autant pour moi, ce n'est peut-être pas tout-à-fait vrai puisque tu recherches une certaine périodicité de répartitions des nombres qui restent, chose qui n'est pas présente dans l'algorithme de Eratosthène, dont la méthode est "bourin", mais mon conseil de séparation entre algorithme et mise en œuvre reste valable.
J'en suis pas sûr. J'ai plutôt pensé à l'usage d'un "et" au lieu d'un "ou". Mais bon, pas besoin de confirmation, y a pas mort d'homme. Ca m'a juste amusé (c'est de bon aloi sur un forum ludique)
Excellent conseil. Bien structurer. Et je dirais même :
- propriétés mathématiques utilisées
- l'algorithme (sans ordinateur)
- implémentation monoprocesseur
- méthode d'implémentation multiprocesseur
A noter que la dernière étape n'est pas triviale en soi. Me rappelle d'un algo multi-thread que j'avais conçu et qui marchait très bien en monoprocesseur ("parallélisme séquentiel") et qui a fait un lamentable BOUM en multi-processeur). Ca vaut la peine de bien la séparer.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Sans vouloir être pessimiste, on est très, très loin de ça... Ne pas réinventer la route, écouter les remarques et éviter de croire qu'un algo, c'est 3 phrases en mode yakofokon sans savoir programmer et encore moins en multi-proc/multi-machines serait un début.
On peut au moins l'aiguiller. Tout progrès sera le bienvenu
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Nombre de 1 à 60: 1, 2, 3, 4, 5, 6, 7 ,8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69
Sans les multiples de 2 (2 exclus): 1,2,3,5,7,9,11,13,15,17,19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69
Sans les multiples de 3 (3 exclus): 1,3,5,7,11,13,17,19,23,25,29,3 5,37,39,41,43,47, 53, 55, 59, 61, 65, 67
Ecart entre les multiples de 5 dans la liste précédente (combien de chiffre entre deux multiples de 5 consécutifs): 6,1,6,2
C'est comme cela que j'ai compris ta phrase et je ne trouve pas que les multiples de 5 soient répartis uniformément dans la liste des nombres naturels sans les multiples de 2 et 3.
Après, je n'ai pas vérifié suffisamment et puis j'ai pu me tromper car j'ai tout fait à la main (et puis c'est long même pour un ordi, puisqu'il faudrait faire le modulo de chaque nombre par 5 et vérifier si cette opération est égal à 0 (à moins que tu ai une meilleur idée)). En tout cas, se serait marrant si la suite était 6,1,6,2,6,3,6,4 ou bien 6,1,6,2,6,4,6,8.
Même si on peut trouver une formule pour les multiples de 5 dans la liste des nombres naturels sans les multiples de 2 et 3, il faudrait calculer la répartition pour les multiples de 7 dans la liste des nombres naturels sans les multiples de 2, 3 et 5 et trouver une formule comme pour la liste précédente.
Et ainsi de suite.
Et si y'avait quelque chose à glaner, y'a longtemps que ça aurait été déjà fait.
bonjour
je donne ci-aprés les nombres restants si on supprime les multiples de de 2 et 3, tu verra qu'ils ont une répartition uniformément répétitive (répartis uniformément)
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143 145 149 151 155 157 161 163 167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215 217 221 223 227 229 233 235 239 241 245 247 251 253 257 259 263 265 269 271 275 277 281 283 287 289 293 295 299 301 305 307 311 313 317 319 323 325 329 331 335 337 341 343 347 349 353 355 359 361 365 367 371 373 377 379 383 385 389 391 395 397 401 403 407 409 413 415 419 421 425 427 431 433 437 439 443 445 449 451 455 457 461 463 467 469 473 475 479 481 485 487 491 493 497 499 503 505 509 511 515 517 521 523 527 529 533 535 539 541 545 547 551 553 557 559 563 565 569 571 575 577 581 583 587 589 593 595 599 601 605 607 611 613 617 619 623 625 629 631 635 637 641 643 647 649 653 655 659 661 665 667 671 673 677 679 683 685 689 691 695 697 701 703 707 709 713 715 719 721 725 727 731 733 737 739 743 745 749 751 755 757 761 763 767 769 773 775 779 781 785 787 791 793 797 799 803 805 809 811 815 817 821 823 827 829 833 835 839 841 845 847 851 853 857 859 863 865 869 871 875 877 881 883 887 889 893 895 899 901 905 907 911 913 917 921 923 927 929 933 935 939 941 945 947 951 953 957 959 963 965 969 971 975 977 981 983 987 989 993 995 999 1001 1005 1007 1011 1013 1017 1019 1023 1025 1029
BONJOUR
Pour une dernière tentative.
Ce qui m’échappe c’est que : quel que soit la méthode qui utilise l’élimination des nombres non premiers pour trouver les premiers s’appellera ERATOSTHENE, alors les autres méthodes n’ont pas de nom.
ERATOSTHENE a utilisé la méthode de « suppression des nombres non premiers pour trouver les premiers » pour faire son algorithme sur une table 2D ne lui donnez par le brevet de cette méthode à tort.
Oui, d'accord, mais le problème c'est qu'on ne voit cette périodicité que lorsqu'on a écrit la liste des nombres, pourras-tu prévoir quelle sera la périodicité des multiples de 7 restants lorsqu'on aura enlevé les multiples de 5 sans les écrire? Et écrire une formule permettant de les prévoir pour n'importe quel nombre? Encore une fois il ne faut pas montrer mais démontrer.
Dernière modification par JPL ; 28/03/2019 à 23h57. Motif: Correction de la balise Quote
