Bonjour
L’obtention des Nombres premiers sans division mais par iterations et disjonctions ensemblistes peut il être plus performant que les méthodes usuelles de divisions successives habituellement utilisées.
Merci de répondre à cette question.
Les méthodes de divisions successives ne sont plus utilisées depuis très longtemps (plus de 2000 ans ?), elles ne sont pas usuelles.
Donc on pourrait envisager raisonnablement de sortir tous les nombres premiers en dessous de 100 millions par programmation sur une tablette Android en un temps inférieur à 25 mn je suppose.
Cela n'a rien à voir avec le fait qu'on n'utilise pas les divisions successives. Mais c'est faisable en quelques secondes au plus avec une technique qui a plus de 2000 ans et qui se code en quelques lignes à dizaines de lignes max (et même pas besoin de coder, on trouve le code sur le Net).Envoyé par Porte7
P.S : je n'ai pas de tablette Android et j'avoue avoir du mal à voir l'intérêt d'utiliser ça pour coder ce genre de chose mais sur ma machine, ça tourne en 0,3 sec en Java.
Bonjour pm42
Pardonnez moi mais si j’ai bien saisi vous sortez 5761455 nombres premiers en 0,3 secondes ?
Oui. On peut probablement aller plus vite.
Vous avez une adresse sur internet pour y trouver le code svp?
J’ai bien cherché sans succès, merci.
J'obtiens un résultat similaire en Pascal (0.25s)
Wikipedia :
Code:Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai Mettre à Faux les cases d'indice pair > 2 L[1] = Faux i=3 Tant que i*i≤Limite Si L[i] Pour j de i*i à Limite par pas de 2*i L[j] = Faux Fin pour Fin si i=i+1 Fin tant que Retourner L Fin fonction
Dernière modification par Garion ; 22/09/2023 à 18h44.
Merci bien.
Je vais essayer l’algorithme en c.
Merci encore.
On peut remplacer cette condition qui calcule le carré de i à chaque tour par "Tant que i <= racine(limite)", la racine de limite n'étant calculée qu'une seule fois
Effectivement le programme écrit en c va très vite.
J’ai eu un problème de pile probablement dès que la limite du calcul est très grande.
Dans tous les cas j’ai remplacé le tableau d’entier par un Tableau de Booléens dans mon programme personnel ce qui a accéléré très fort la vitesse d’exécution.
Merci.
Il ne faut pas créer le tableau sur la pile. sinon, je ne vois pas comment il explose la pile.
Il faut utiliser malloc (allocation sur le heap) et non alloca (allocation sur la pile, rapide, dangereux, etc..)...
avec le source ce serait plus clair.
Jusqu'ici tout va bien...
Bonjour polo
On va pas bien loin dans l’intervalle de recherche ici.Code:J’ai démarré avec ça : #include<stdio.h> #include <stdlib.h> #include <math.h> #include<conio.h> #include <time.h> #include <new> int main(int argc, char *argv[]) { int limite; printf("Saisir la limite de recherche des nombres premiers: "); scanf("%d",&limite); time_t debut = time(NULL); bool Tableaumultiple[limite]; Tableaumultiple[0] = true; // 0 n'est pas premier Tableaumultiple[1] = true; // 1 n'est pas premier for (long int i=2; i<limite; i++) Tableaumultiple[i] = false; for (long int i=2; i<limite; i++) if (!Tableaumultiple[i]) { long int multiple = 2 * i; while (multiple < limite) { Tableaumultiple[multiple] = true; multiple =multiple + i; } } for (int i=0; i<limite; i++) if (!Tableaumultiple[i]) { printf(" \n i : %d",i); } time_t fin = time(NULL); printf (" Durée de la recherche : %d seconde(s)", (fin - debut)); }
Puis j’ai du utiliser ensuite l’opérateur new....
Je recherche dans la journée si je retrouve le programme.....
Je joindrai une copie d’écran annonçant une erreur de segment sur une recherche de 10000000.
Merci A+
Dernière modification par JPL ; 26/09/2023 à 15h28. Motif: Ajoute de la balise Code pour garder l’identation
Désolé de pas pouvoir mieux faire car j’ai plus de bouquins, ni pc, ni compilateur pour créer un exe, ni cerveau en état de marche et qui commence à vieillir))
Pour ma part, j'ai implémenté le crible d'Ératosthène en java mais pour les grands nombres je n'ai pas assez de RAM, donc j'ai aussi implémenté un algo qui consiste à utiliser l'opérateur modulo pour tester la primalité de chaque entier jusqu'à le nombre limite.
Il y a des techniques pour ça :
http://compoasso.free.fr/primelistwe...it%20composite).
Depuis le temps qu'on cherche, on n'a pas encore réussi à les trouver ces nombres premiers ?
On a trouvé les premiers mais pas les derniers...Depuis le temps qu'on cherche, on n'a pas encore réussi à les trouver ces nombres premiers ?
Jusqu'ici tout va bien...
Bonjour,
J’imaginerai bien faire un algorithme basé sur cette observation d’après la photo ci- jointe
La première ligne donne tous les NP avec leurs multiples.
Les lignes suivantes donnent tous les multiples possibles.
Mais bon c’est certainement inutile!
Salut,
Ca fait très "crible d’Ératosthène" et ses très nombreuses variantes (spirales d'Ulam et autres arrangements et règles pour y mettre les nombres). Ca été tellement trituré dans tous les sens (souvent par des amateurs d'ailleurs vu que c'est facile) qu'il ne doit pas y avoir beaucoup de chose à en tirer. En tout cas pas sans un fil conducteur sûr et solide. Et pour une génération de tous les nombres premiers à la suite on trouve quelques algorithmes costaud sur le net (ne nécessitant pas de stocker un énorme tableau, souvent le talon d'Achille de cette méthode).
Mais rien ne t'empêche de faire un algo pour essayer. C'est toujours sympa à faire et pas très difficile. L'expérimentation, ça peut donner des idées
Et la recherche d'optimisation toujours sympa (enfin, quand on aime ça évidemment).
Ce qui est sympa a faire aussi ces des algos de test de primalité pour de très grands nombres. Et aussi la génération de très grands nombres premiers (extrêmement utile pour les algos de cryptographie).
Et aussi de factorisation des nombres (implémenter le calcul avec les courbes elliptiques, ça c'est un beau challenge).
J'ai joué un peu à ça étant gamin (mais j'étais surtout fan des analyses arborescentes pour les jeux, je suis le roi de l'alpha-bêta, et les différentes techniques d'apprentissage. Ainsi que l'écriture de moteurs de calculs symboliques.... en BASIC, hé oui, j'étais courageux
EDIT quand je dis gamin, c'est autour de mes 15 ans et après, pas en primaire hein
Dernière modification par Deedee81 ; 10/10/2023 à 06h48.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Vous avez raison deedee je vais même aller plus loin, ça me détendra
Tout nombre qui s’écrit suivant les formules suivantes:
A( i , j ) = (6*i + 1)*(6*j + 1) ± 2 avec j >= i
B ( i , j ) = (6*i + 1)*(6*j + 5) ± 2 avec j >= i
C ( i , j ) = (6*i + 5)*(6*j +5) ± 2 avec j >= i
D ( i , j ) = (6*i + 5)*(6*j + 1) ± 2 avec j > i
S’il n’est pas divisible par 2 ou 3 est-il un nombre premier?
.........Le temps de faire un petit programme
Dernière modification par Porte7 ; 12/10/2023 à 13h32.
Vu que c'est symétrique en i et j (comme C), j>=i n'a aucun impact.
6*i est pair, 6*i+1 est donc impair. Idem pour l'autre terme. Donc le produit est impair. Ce que je suppose être +/- 2 donne donc un impair.
La divisibilité par 2 va être compliquée.
et (6*10+1)*(6*11+1)+2 = 4089 qui n'est pas premier.
Oui mais il est divisible par 3. Mais je doute que ce soit toujours premier même si c'est non divisible par 3. C'est bien la première fois qu'on aurait une formule aussi simple. Faut juste un autre contre-exemple
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
En même temps, (6*i+1)*(6*j+1)+2 est toujours divisible par 3. Au temps pour moi.
Avec le -2, on trouve des contre-exemples facilement: 4,4 => 623 = 7x89 (sauf autre erreur de ma part, je suis un peu concentré au boulot)
Dernière modification par pm42 ; 12/10/2023 à 15h53.
En effet pm42 il semblerait que les multiples jumeaux posent problème
Ex 121 et 119
145 et 143
625 et 623 etc.....
J’avais envie de rajouter la divisibilité par 5 à celle de 2 et 3.
Mais bon !!!!!
Salut,
Sur wikipedia on trouve pas mal de formules simples donnant des nombres premiers. Cela a beaucoup été cherché par des mathématiciens et des amateurs (depuis des siècles !!!) Il est donc (très) improbable d'en trouver une qui marche. Celle données dans wikipedia ne donnent qu'un nombre limité de nombre premiers ou alors les donnent tous (mais sont loin d'être aussi simple dans ce cas) mais sont inutilisables (temps de calcul astronomique).
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
En effet et c'est une constante de la "recherche amateur" telle qu'elle est publiée sur le forum : même dans le meilleur des cas, beaucoup de temps est passé à rechercher des choses dont on sait qu'elles ne marchent pas le plus souvent et pas assez à lire ne serait ce que les pages Wikipedia et à vérifier les "résultats".
De toute façon c'est toujours un bon conseil à donner : se documenter
C'est d'ailleurs vrai pour les pros et pas qu'en math. Tout travail de recherche commence par un paquet de bibliographie. Avec 8 milliards d'habitants. Y a VRAIMENT intérêt à vérifier ce qui a déjà été fait
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Bonjour,
Pour finir je vais enlever quand même la division par 2 .......ça fait mauvais genre de la laisser
Pour finir je vais enlever quand même la division par 2 .......ça fait mauvais genre de la laisser
Et puisque le titre est "performance", oui, vaut mieux
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
