π
<-
Chat plein-écran
[^]

algorithme test nombres premiers entre eux

Pour le TI-Basic sur Nspire

algorithme test nombres premiers entre eux

Message non lude kadtexas » 27 Déc 2018, 16:59

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.
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: algorithme test nombres premiers entre eux

Message non lude UnCurieux » 27 Déc 2018, 19:04

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é :/
Maths, fractales, géométrie, packs de levels Oiram, jeux, physique, ... : ici

ImageImage
Avatar de l’utilisateur
UnCurieuxProgrammeur
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Prochain niv.: 23.7%
 
Messages: 367
Images: 2
Inscription: 19 Mai 2017, 18:20
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: Prépa scientifique 1A

Re: algorithme test nombres premiers entre eux

Message non lude Hisham » 28 Déc 2018, 08:59

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 ... :D

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 ;)
Avatar de l’utilisateur
HishamPremium
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 10.5%
 
Messages: 139
Inscription: 01 Mar 2017, 20:52
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: algorithme test nombres premiers entre eux

Message non lude kadtexas » 28 Déc 2018, 18:49

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:
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 !
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: algorithme test nombres premiers entre eux

Message non lude loupiot » 28 Déc 2018, 22:49

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 :D
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 :D

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 ;)
Avatar de l’utilisateur
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 1.9%
 
Messages: 158
Images: 4
Inscription: 30 Oct 2015, 13:23
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 2A ENS Lyon maths

Re: algorithme test nombres premiers entre eux

Message non lude kadtexas » 29 Déc 2018, 11:26

Merci loupiot pour la réponse!

Cela me parait un peu complexe mais j'essayerai...
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: algorithme test nombres premiers entre eux

Message non lude loupiot » 29 Déc 2018, 15:51

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
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
Avatar de l’utilisateur
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 1.9%
 
Messages: 158
Images: 4
Inscription: 30 Oct 2015, 13:23
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 2A ENS Lyon maths

Re: algorithme test nombres premiers entre eux

Message non lude kadtexas » 29 Déc 2018, 16:52

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.
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Re: algorithme test nombres premiers entre eux

Message non lude loupiot » 29 Déc 2018, 17:01

oui, c'est le naïf qui est codé ci dessus. Je ne pense pas que ce que j'avais proposé soit plus performant
Avatar de l’utilisateur
loupiotProgrammeur
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 1.9%
 
Messages: 158
Images: 4
Inscription: 30 Oct 2015, 13:23
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 2A ENS Lyon maths

Re: algorithme test nombres premiers entre eux

Message non lude kadtexas » 29 Déc 2018, 17:46

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 ?
Avatar de l’utilisateur
kadtexas
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 73.8%
 
Messages: 283
Inscription: 29 Jan 2015, 19:32
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: etudiant

Suivante

Retourner vers Nspire-Basic

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 8 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1185 utilisateurs:
>1167 invités
>12 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)