Nombres premiers
Utilisateur anonyme -
Bonjour,
Je suis en train de faire un programme python pour calculer les nombres premiers :
max = int(input("Jusqu'à combien veux-tu que je calcule les nombres premiers ? "))
for i in range(2, max + 1):
diviseur = 0
for j in range(2, max):
if i % j == 0:
diviseur + 1
if diviseur == 0:
print(i)
else:
break
Quand je lance le programme, il renvoie :
2
3
4
5
6
7
8
9
10
... comme s'il ne prenait pas en compte les instructions que je lui donnais.
Pouvez-vous m'aider ?
11 réponses
-
Salut,
Admettons que i en est à 3 dans ta 1ère boucle, premier nombre premier donc, que se passe-t-il lors de ta boucle for avec j ?
Forcément i % j vaudra 0 lorsque j sera également à 3, il y a donc une erreur de raisonnement quelque part ^^ -
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
bonjour,
as-tu envisagé d'imprimer la valeur de "diviseur" avant et après la ligne 6?
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
Moi je dirais: "c'est comme si tu avais écrit des instructions sans prendre en compte le résultat attendu".
-
Tu as raison, il me dit que c'est toujours égale à 0 avant et après la ligne 6, je comprenais déjà pas avant que tu me répondes mais là je suis complètement perdu, je ne comprends pas où est ce que j'ai pu me tromper
-
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
Merci beaucoup de ta réponse, je n'avais pas vu cette erreur qui était pourtant assez basique, en tout cas merci encore de m'avoir aidé
-
Bonsoir
je me permets une petite correction
Admettons que i en est à 3 dans ta 1ère boucle, premier nombre premier donc,
2 est aussi un nombre premier.
Ils est divisible par 1 et par lui même.
-
Parmi les erreurs que j'ai pu voir
- La valeur de départ de i ne permet pas de voir que 1 est premier
- La valeur de fin de j n'a pas de raison de dépasser racine(i). Tu peux utiliser la fonction isqrt.
- Tu confonds diviseur est reste. Un nombre i est divisible par j si le reste de la division i par j est nul. Or ton teste porte sur le diviseur. Pour rappel, le reste de la division de i par j s'obtient avec l'opérateur module (%)
reste = i % j
- L'incrément n'est pas correct Si tu écris juste :
diviseur + 1
... la valeur de ta variable n'est pas modifiée, car cette valeur n'est pas stockée. Il faudrait plutôt écrire :
diviseur += 1
- Le test où tu regardes le reste n'est pas dans la bonne boucle. Ton break devrait être dans la boucle for j (si j est un diviseur de i, alors nul besoin de considérer les valeurs suivantes de j). Or avec ton indentation le test est fait dans la boucle for i.
- Il y a une erreur de raisonnement dans ton programe. Pour rappel, un entier i est premier si aucun entier j compris entre 1 et racine(i) de divise i. Cela signifie que soit tu détectes dans ta boucle for j que i est non premier (car tu as trouvé un diviseur j), soit à la fin de la boucle, tu n'as trouvé aucun diviseur et donc i est premier.
Bonne chance
-
Bonsoir mamiemando
- La valeur de départ de i ne permet pas de voir que 1 est premier
Il semble que 1 ne soit pas premier, car selon plusieurs sites que j'ai consulté avant de répondre plus haut, un nombre premier admet 2 diviseurs distincts, 1 et lui-même, or 1 et 1 ne sont pas distincts.
Pour le reste, je suis d'accord avec toi, même si je doute que le fait de s'arrêter à racine(i) coule de source pour FICTIFBonsoir,
Puisqu'on pinaille, en effet 1 n'est plus considéré comme premier comme ce fut le cas à une époque.
Mais le fait qu'un nombre entier ne puisse admettre aucun diviseur supérieur à sa racine n'est pas sa définition mais la démonstration sur la base de cette définition que tout nombre non premier au moins égal à 2 admet un diviseur premier au plus égal à la partie entière de sa racine carrée.
La définition à proprement parler des nombres premiers (et sans évoquer certains types particuliers) répond à ce que Whismeril a indiqué tout au moins dans l'ensemble des entiers naturels.
Bonjour,
cette précision me.rassure quelque part car quand j'ai lu
i en est à 3 dans ta 1ère boucle, premier nombre premier donc
je me suis dit, qu'est ce qu'il raconte lui? Y'a 1 et 2 aussi. Mais quand même ça m'a mis le doute d'où un petit tour (rapide et en diagonale) dans un certain nombre de sites sérieux.
Mais je n'ai pas compris dans ces recherches que la définition du nombre premier avait évolué avec le temps. Si même les maths varient où va t on?Bonjour,
Je n'ai plus la date en tête, de mémoire 1 a été considéré comme premier jusqu'à la fin du 19ème siècle; en dehors de l'aspect purement sémantique pour nous autres béotiens, considérer aujourd'hui que 1 est premier invaliderait un certain nombre de théorèmes à commencer par le théorème fondamental de l'arithmétique et y compris certaines applications pratiques (comme par exemple le calcul de clés cryptographiques).
L'exemple le plus frappant de la relativité des maths est du à Lobatchevski (qui a considéré que par un point donné il passait 2 droites) puis Riemann (pour qui il y en a une infinité) et contredisant tous deux l'axiome d'Euclide, mais il est vrai du fait que ce dernier se limitait à 2 dimensions.
-
Bonjour, petit précision que je voulais vous apporter en plus de remerciement, un nombre premier est un nombre qui a seulement deux diviseur qui sont souvent 1 et lui même. Ce qui fait que 1 est un exception car 1 et lui même sont les même chiffres donc, il n'a qu'un diviseur ce qu'il fait qu'il n'est pas premier. Par contre 2 respecte bien la règle et fait partie des nombres premiers.
-
Bonjour,
On peut aussi faire ça:
def est_premier(n): for k in range(2,n): if(not n%k): return(True) return(False) maxi = int(input("Jusqu'à combien veux-tu que je calcule les nombres premiers ? : ")) for k in range(maxi+1): if(est_premier(k)): print(k)-
Bonjour Phil_1857
Merci pour ta réponse mais malheureusement le code est incorrect (par exemple ta fonction considère que 10 est premier) car le test est écrit "à l'envers".
Voici un code fonctionnel :
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import sys from math import isqrt def is_prime(n: int) -> bool: """ Teste si un nombre n est premier. Args: n(int): Le nombre à tester. Returns: ``True`` si est seulement si n est premier. """ if not isinstance(n, int) or n <= 1: return False for i in range(2, isqrt(n) + 1): if n % i == 0: return False return True # Saisie de la borne supérieure n_max = None while not (isinstance(n_max, int) and n_max > 0): try: n_max = int(input("Saisir un entier > 0: ")) except ValueError: print("Saisie invalide", file=sys.stderr) # Calcul des nombres premiers dans {0, ..., n_max - 1} primes = { n for n in range(n_max) if is_prime(n) } print(primes)Résultat
Saisir un entier > 0: 100 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}À noter qu'il faut bien itérer jusqu'à isqrt(n)+1 car si on prend 4, isqrt(n) vaut 2 et range(isqrt(n)) n'itérera pas jusqu'à 2, valeur dont il faut tenir compte. Le problème se pose plus généralement pour tous les carrés.
Bonne chance
-
-
Personnellement, à la fin j'ai tourné ça comme ça :
max = int(input("Jusqu'à combien veux tu que je calcule les nombres premiers : ")) liste_de_nombres_premiers = [] for i in range(2, max + 1): diviseur = 0 for d in range(2, i): if i % d == 0: diviseur = 1 if diviseur == 0: liste_de_nombres_premiers.append(i) k = int(input("Le combientième nombre premier veux-tu que je te donne ? ")) print(liste_de_nombres_premiers[k]) print(liste_de_nombres_premiers)
-
Merci pour ton retour et félicitations, car ton code marche :-) Quelques recommandations toutefois :
- Pense à mettre le code en forme
- Pense à basculer le sujet en résolu quand tu as tes réponses (nécessite un compte CCM).
- diviseur est en réalité un booléen, il serait donc plus logique de l'initialiser à False et de le basculer en cas de besoin à True. De plus le nom est confusant, car il ne s'agit pas d'un diviseur, mais plutôt du test indiquant si le nombre est premier ou pas. Il serait donc plus logique de renommer cette variable est_premier par soucis de lisibilité. Dans ton code, c'est d qui joue le rôle de diviseur.
- Il est contre-indiqué de nommer une variable max, car c'est une fonction de python (qui comme son nom l'indique, calcule le max d'un itérable, par exemple une liste de valeurs).
- Tu peux effectivement considérer pour d les valeurs de 0 à i, mais en réalité, il suffit de tester les valeurs dans {2, ..., int(racine(i)) + 1}. En effet, si i n'est pas premier, alors il a au moins un diviseur compris dans cet ensemble. Cela permet ainsi d'accélérer le code, puisqu'on teste moins de diviseurs.
Bonne continuation
-
-
Bonjour Mamie,
Damned ! Tu as raison !
Je me suis fait avoir comme un bleu !
def est_premier(n): if(n <= 1): return(False) for k in range(2,n): if(not n%k): return(False) return(True) maxi = int(input("Jusqu'à combien veux-tu que je calcule les nombres premiers ? : ")) for k in range(maxi): if(est_premier(k)): print(k)
