Bonjour
Pour tester des entiers a,b,c,d,... s'ils sont premiers entre eux deux à deux, on peut faire comme suit:
tester a et b
tester a et c
tester a et d
.....
tester b et c
tester b et d
.......
tester c et d etc...
Je me demande s'il n'y a pas mieux !
Merci pour une aide.
algorithme test nombres premiers entre eux
-
kadtexas
Niveau 9: IC (Compteur Infatigable)- Messages: 283
- Inscription: 29 Jan 2015, 19:32
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: etudiant
Re: algorithme test nombres premiers entre eux
Tu peux trouver si un nombre est premier, s'il l'est il sera premier avec n'importe quel autre nombre je suppose, donc tu n'auras pas à le tester avec un autre nombre.
Sinon en utilisant ce que tu as proposé, pour gagner du temps tu gardes en mémoire (dans une liste par exemple) les diviseurs de a par exemple, comme ça pas besoin de les recalculer pour chaque test.
Je ne suis pas sûr d'avoir été d'une grande aide, désolé :/
Sinon en utilisant ce que tu as proposé, pour gagner du temps tu gardes en mémoire (dans une liste par exemple) les diviseurs de a par exemple, comme ça pas besoin de les recalculer pour chaque test.
Je ne suis pas sûr d'avoir été d'une grande aide, désolé :/
-
UnCurieuxProgrammeur
Niveau 11: LV (Légende Vivante)- Messages: 367
- Images: 2
- Inscription: 19 Mai 2017, 18:20
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: Prépa scientifique 1A
Re: algorithme test nombres premiers entre eux
kadtexas a écrit:Bonjour
Pour tester des entiers a,b,c,d,... s'ils sont premiers entre eux deux à deux, on peut faire comme suit:
tester a et b
tester a et c
tester a et d
.....
tester b et c
tester b et d
.......
tester c et d etc...
Je me demande s'il n'y a pas mieux !
Merci pour une aide.
Hi @kadtexas,
if your talking 'bout GCD … then yeah … GCD can only accept two "entries" at a time … so you have to find the GCD of the first two values … then find the GCD of your answer and the third value … and so on …
When two or more numbers got 1 as their GCD ... then they are "coprimes" ... ah ah ah ...
Example: 6 - 9 - 25
GCD(6,9) = 3
GCD(3,25) = 1
So the GCD(6,9,25) = 1 hence 6, 9, 25 are coprimes …
Happy New Year
-
HishamPremium
Niveau 8: ER (Espèce Rare: nerd)- Messages: 139
- Inscription: 01 Mar 2017, 20:52
- Genre:
- Calculatrice(s):→ MyCalcs profile
Re: algorithme test nombres premiers entre eux
Bonjour Hisham et merci pour ta réponse.
Comme je ne connais pas l'anglais j'ai fait traduire ta réponse par traducteur en ligne:
Je pense que je peux donner un contre-exemple:
4,7,21
gcd(4,21)=1
gcd(1,21)=1
alors que gcd(7,21)=7, donc 7, 21 ne sont pas premiers entre eux ? Cela ne répond pas à ma question !
Comme je ne connais pas l'anglais j'ai fait traduire ta réponse par traducteur en ligne:
si vous parlez de GCD… alors oui… GCD ne peut accepter que deux «entrées» à la fois… vous devez donc trouver le GCD des deux premières valeurs… puis trouver le GCD de votre réponse et la troisième valeur… etc. …;)
Lorsque deux numéros ou plus ont 1 comme numéro de code général de panier, ils sont alors des "coprimes" ... ah ah ah ...: D
Je pense que je peux donner un contre-exemple:
4,7,21
gcd(4,21)=1
gcd(1,21)=1
alors que gcd(7,21)=7, donc 7, 21 ne sont pas premiers entre eux ? Cela ne répond pas à ma question !
-
kadtexas
Niveau 9: IC (Compteur Infatigable)- Messages: 283
- Inscription: 29 Jan 2015, 19:32
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: etudiant
Re: algorithme test nombres premiers entre eux
au lieu de tous les comparer deux à deux, je pense qu'il est préférable de prendre le plus petit entier de ta liste, disons n1, et de créer une liste qui comprends tous les diviseurs premiers de n1 (avec la valuation p-addique, c'est à dire qu si 2^m divise n1 (m maximal), tu y mets m fois 2). Je pense qu'il faut regarder le plus petit entier disponible, car le test des diviseurs premiers devrait être plus rapide.
Ensuite, tu regardes l'entier suivant, disons n2, et tu enlève de ta liste les nombres premiers qui ne divisent pas n2. La seule difficulté est alors de gérer la répétition des nombres dans la liste (2 est présent m fois si 2^m divise n1).
Pour contrer cela, je te conseillerais d'arranger ta liste dans l'ordre croissant et de créer un compteur (ça devient un peu complexe c'est vrai) :
Initialise ton compteur à 1, parcours la liste par i, si le nombre premier que tu as est identique au précédent, tu incrémente ton compteur de 1, sinon tu le réinitialise à 1. Regarde si i^compteur divise ton n2, si oui continue, sinon, enlève tous les représentent suivant de ce nombre premier de la liste.
Et tu continue
Je pense que c'est plus efficace, ça t'évite de faire n*(n-1)/2 comparaison. C'est par contre un peu plus difficile à mettre en place
récapitulatif :
prendre le minimum des nombres qui te sont donner, faire sa décomposition en facteurs premiers, arranger cette liste dans l'ordre croissant, pour chaque nombre qui te sont donner, vérifier, à l'aide de la méthode déjà expliquer si i^compteur divise ton nombre.
A la fin, tu fais le produits de ce qui reste dans la liste. Si quelqu'un a des conseils, je suis preneur
Ensuite, tu regardes l'entier suivant, disons n2, et tu enlève de ta liste les nombres premiers qui ne divisent pas n2. La seule difficulté est alors de gérer la répétition des nombres dans la liste (2 est présent m fois si 2^m divise n1).
Pour contrer cela, je te conseillerais d'arranger ta liste dans l'ordre croissant et de créer un compteur (ça devient un peu complexe c'est vrai) :
Initialise ton compteur à 1, parcours la liste par i, si le nombre premier que tu as est identique au précédent, tu incrémente ton compteur de 1, sinon tu le réinitialise à 1. Regarde si i^compteur divise ton n2, si oui continue, sinon, enlève tous les représentent suivant de ce nombre premier de la liste.
Et tu continue
Je pense que c'est plus efficace, ça t'évite de faire n*(n-1)/2 comparaison. C'est par contre un peu plus difficile à mettre en place
récapitulatif :
prendre le minimum des nombres qui te sont donner, faire sa décomposition en facteurs premiers, arranger cette liste dans l'ordre croissant, pour chaque nombre qui te sont donner, vérifier, à l'aide de la méthode déjà expliquer si i^compteur divise ton nombre.
A la fin, tu fais le produits de ce qui reste dans la liste. Si quelqu'un a des conseils, je suis preneur
-
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)- Messages: 158
- Images: 4
- Inscription: 30 Oct 2015, 13:23
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: 2A ENS Lyon maths
Re: algorithme test nombres premiers entre eux
Merci loupiot pour la réponse!
Cela me parait un peu complexe mais j'essayerai...
Cela me parait un peu complexe mais j'essayerai...
-
kadtexas
Niveau 9: IC (Compteur Infatigable)- Messages: 283
- Inscription: 29 Jan 2015, 19:32
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: etudiant
Re: algorithme test nombres premiers entre eux
J'ai mis en places les deux codes, et il s'avère que l'algorithme naïf n'est pas si mauvais. Le deuxième algorithme est performant si tu as déjà une liste des premiers, de préférences gros (on doit atteindre tous les premiers inférieurs ou égaux au plu gros nombre de ta liste).
Et si tu rentre des nombres très gros, calculer le pgcd ne pose en général pas de problème (complexité logarithmique), mais décomposer en facteurs premiers si ... donc l'algorithme que je t'ai proposé n'est pas du tout efficace pour de gros nombres
Ton code se construira comme cela :
tu prends une liste de nombre
si la liste est vide, on ne renvoie rien, si la liste contient un élément, on renvoie cet élément.
tu crées une variable m qui vaut le pgcd tu premier et deuxième élément de la liste
Et si tu rentre des nombres très gros, calculer le pgcd ne pose en général pas de problème (complexité logarithmique), mais décomposer en facteurs premiers si ... donc l'algorithme que je t'ai proposé n'est pas du tout efficace pour de gros nombres
Ton code se construira comme cela :
tu prends une liste de nombre
si la liste est vide, on ne renvoie rien, si la liste contient un élément, on renvoie cet élément.
tu crées une variable m qui vaut le pgcd tu premier et deuxième élément de la liste
- Code: Tout sélectionner
i parcourt la liste
j parcourt la liste
m=min(m,pgcd(i,j))
si m=1, alors on peut s arrêter (return m, cela arrivera souvent si tu rentres beaucoup de nombres)
return m
-
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)- Messages: 158
- Images: 4
- Inscription: 30 Oct 2015, 13:23
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: 2A ENS Lyon maths
Re: algorithme test nombres premiers entre eux
J'ai déjà commencé mon algorithme "naïf" et je vais voir ce cela donne.
L'algorithme ci dessus, c'est le naïf ?
Il m'a l'air d'être cours, je l'essayerai après.
Pour ton deuxième algo (plus performant) on en discutera après.
L'algorithme ci dessus, c'est le naïf ?
Il m'a l'air d'être cours, je l'essayerai après.
Pour ton deuxième algo (plus performant) on en discutera après.
-
kadtexas
Niveau 9: IC (Compteur Infatigable)- Messages: 283
- Inscription: 29 Jan 2015, 19:32
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: etudiant
Re: algorithme test nombres premiers entre eux
oui, c'est le naïf qui est codé ci dessus. Je ne pense pas que ce que j'avais proposé soit plus performant
-
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)- Messages: 158
- Images: 4
- Inscription: 30 Oct 2015, 13:23
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: 2A ENS Lyon maths
Re: algorithme test nombres premiers entre eux
- Code: Tout sélectionner
m=min(m,pgcd(i,j))
Je pense que c'est: m=min(m,pgcd(liste[i],liste[j]))
C'est quoi m ? le plus petit de la liste ? Si oui, faut il ordonner la liste en croissance ?
-
kadtexas
Niveau 9: IC (Compteur Infatigable)- Messages: 283
- Inscription: 29 Jan 2015, 19:32
- Genre:
- Calculatrice(s):→ MyCalcs profile
- Classe: etudiant
18 messages
• Page 1 sur 2 • 1, 2
Qui est en ligne
Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 8 invités