Python nombre premier

[JohannLiebert]

Bonjour,
J'ai un exercice en python que je n'arrive pas à faire. Vous avez l'énoncé de mon exercice et voici mon code :

def premier(x):
    for i in range (2,x):
        if x%i==0:
            return False
        else:
            return True
def prime_numbers(nb):
    x=1
    list=[]
    if nb<0 or nb is not int:
        return None
    elif nb==0:
        return list
    else:
        while len(list)!=nb:
            x = x + 1
            y=premier(x)
            if y is True:
                list.append(x)
        return list
/code

Je vous demande de l'aide car je ne comprends pas pourquoi mon code ne fonctionne pas. Merci d'avance.

-----

[pm42]

4 choses :

- il est important d'utiliser les balises CODE autour de ton code pour que ça soit lisible et pour garder l'indentation. Sans cela, cela complique la lecture et cela rend plus difficile de t'aider
- la dernière fois que tu as posé une question, tu as eu des réponses mais tu n'es pas revenu : https://forums.futura-sciences.com/l...on-turtle.html. Là aussi, cela n'incite pas à faire un effort
- pour ton exo, pourquoi ne pas utiliser un crible d'Eratosthène qui sera infiniment plus efficace ?
- si tu veux vraiment tester si on nombre est premier en regardant tous les diviseurs, pourquoi aller jusqu'a lui même -1 ? Il suffit de tester jusqu'à sa racine carrée.

[JPL]

Balise ajoutée.

[pm42]

Pour le crible d'Eratosthène, je reconnais qu'il faudrait sans doute utiliser la fonction qui donne une évaluation du nième nombre premier ce qui n'est pas forcément connu.

Quand à ton code : "is not int" est toujours vrai.

Ce qui amène au point suivant : tous les outils modernes intègrent un débugger qui permet de faire du pas à pas et de trouver ce genre d'erreur.
Je te conseille vivement de t'y intéresser.

[A voir en vidéo sur Futura]

[Ernum]

Salut,

def premier(x):
     for i in range (2,x):
         if x%i==0:
             return False
         else:
             return True

Le nom que tu donnes à tes fonctions doivent être le plus explicite possible, j'en déduis que tu pensais discriminer(*) les nombres premiers ici?
Or, là, la fonction je l'aurais nommée autrement ... .

(*): désolé si le vocabulaire employé n'est pas des plus juste, n’hésitez pas à me le faire savoir.

[JohannLiebert]

enfaite là je voulais juste voir si x est un nombre premier ou pas.

[JohannLiebert]

Merci de ta réponse. Je vais voir pour le crible d'Eratosthène. Et désolé, j'avais complètement oublié de te répondre.

[polo974]

Question:
À quoi sert le for si au premier tour, QUELQUESOIT le résultat du if tu fait un return ?

(cette question doit te permettre de trouver l'erreur...)

[pm42]

Question:
À quoi sert le for si au premier tour, QUELQUESOIT le résultat du if tu fait un return ?

(cette question doit te permettre de trouver l'erreur...)

En effet mais son code ne va même pas jusque là.

[JohannLiebert]

oui merci j'ai compris j'ai fais n'importe quoi

[pm42]

oui merci j'ai compris j'ai fais n'importe quoi

Non, ton code est pas mal pour un débutant mais c'est normal d'avoir à corriger ce genre d'erreurs. On a vu pire.

[Garion]

Maintenant, au niveau optimisation on peut faire mieux.
"x = x + 1" il serait mieux de mettre "x = x + 2" comme ça, on ne teste que les nombres impairs.
(et gérer le cas spécial du nombre "2").
Et plutôt que de diviser par tous les nombres entre 2 et x, tu pourrais essayer de diviser uniquement par les nombres déjà trouvé dans ta liste.
Pour finir, je ne connais pas bien python, mais "if y is True:" n'est-il pas un pléonasme ? On ne peut pas écrire "if y:" en Python ? y étant déjà un booléen.

[Garion]

Et dernière optimisation, il n'est pas nécessaire d'essayer de diviser par des nombres supérieurs à la racine carré du nombre testé

[pm42]

Et dernière optimisation, il n'est pas nécessaire d'essayer de diviser par des nombres supérieurs à la racine carré du nombre testé

Peut-être que lire le fil éviterait de répéter des choses déjà dites.

[Garion]

Soit, mais mes deux autres optimisations sont importantes aussi. Surtout la 2eme quand on essaie d'aller loin.
Vaut mieux ajouter des informations quitte à en répéter que ne pas le faire.

[Garion]

Le crible d’Ératosthène reste bien sûr plus performant, mais plus gourmand en terme de mémoire (pour des raisons de performance un booléen est stocké en tant que Word 64 bits dans la majorité des langages compilés en 64 bits, et si on n'utilisait qu'un bit, on aurait un vrai problème de performance), et permet de donner les nombres premiers entre 0 et n. Tandis que l'algo classique permet de dire je veux n nombres premiers ce qui n'est pas possible avec le premier.

[Garion]

En fait, j'ai un peu abusé, il y a des langages compilés qui utilise un octet voire un demi-octet pour stocker un bit.

[pm42]

En fait, j'ai un peu abusé, il y a des langages compilés qui utilise un octet voire un demi-octet pour stocker un bit.

Et ici, on a un débutant qui fait du Python donc le truc où il y a marqué à l'entrée "par moi, l'on va vers les programmeurs perdus, par moi, l'on va vers les boucles lentes, vous qui entrez, renoncez à toute performance".
Et qui se bat avec des concepts de base donc les optimisations mémoire, ça peut attendre.

Et même avec un mot de 64 bits par booléen, on peut facilement faire un million de premiers et plus sur une machine actuelle sans forcer : ça me prend 10 sec en Python standard et consomme moins de 200 Mo.

Et ça prend moins d'une seconde en ajoutant simplement un @njit pour faire du numba et donc compiler à la volée de manière transparente. On pourrait aussi faire du Jython ou n'importe quelle solution qui compile du Python.

[polo974]

En effet mais son code ne va même pas jusque là.

J'avoue n'avoir pointé que le truc qui me sautait aux yeux sur mon petit téléphone...

Non, ton code est pas mal pour un débutant mais c'est normal d'avoir à corriger ce genre d'erreurs. On a vu pire.

Et là, je dois avouer que parfois je commets des trucs assez terrifiants quand je me relis/debugue, donc ce n'est pas réservé au débutant (même si on essaie toujours de mettre la faute sur le dos du stagiaire ).

[Garion]

Et ici, on a un débutant qui fait du Python donc le truc où il y a marqué à l'entrée "par moi, l'on va vers les programmeurs perdus, par moi, l'on va vers les boucles lentes, vous qui entrez, renoncez à toute performance".
Et qui se bat avec des concepts de base donc les optimisations mémoire, ça peut attendre.

Les plus gros gains sont en algorithmique, donc donner des conseils sur la manière d'optimiser du code, ça n'est jamais inutile.

Et même avec un mot de 64 bits par booléen, on peut facilement faire un million de premiers et plus sur une machine actuelle sans forcer : ça me prend 10 sec en Python standard et consomme moins de 200 Mo.
Et ça prend moins d'une seconde en ajoutant simplement un @njit pour faire du numba et donc compiler à la volée de manière transparente. On pourrait aussi faire du Jython ou n'importe quelle solution qui compile du Python.

Pour être précis, avec un implémentation monothread à l'arrache (écrit en 5mn) en langage compilé, il me faut 4ms pour calculer tous les nombres premiers de 0 à 1M et 140 ms pour en calculer 1M (soit une limite définie à 30M dans l'algo).

Maintenant si on veut comparer les langages, passer 10s pour un truc qui peut se calculer entre 4 et 140ms à l'arrache (vu ta mémoire consommé, on est plutôt dans les 4ms de mon cas), c'est une absurdité au niveau d'un utilisateur qui attend mais aussi une absurdité énergétique.
On a dépensé environ plusieurs centaines fois plus d'énergie pour le même résultat, on s'étonne après de la consommation des ordinateurs dans le monde et du besoin d'acheter des tonnes RAM.

[pm42]

Pour calculer un 1M de nombres premiers, il faut un tableau de booléen de 30M de booléens.

Pourquoi ? Le millionème 1er est 15 485 863 donc il faut un peu plus de 15 millions de booléens. J'ai pris 16 millions.

Tu m'expliquera comment 30M de booléen de 64 bits

Pas besoin d'expliquer, on alloue, on calcule et on demande à Python combien de place prend le dit tableau avec sys.getsizeof.
Et ça répond 128000064 donc 128 Mo.
L'OS lui donne un peu plus de 200 Mo pour le process.

Tu n'aurais pas confondu les nombres premiers entre 0 et 1M et 1M de nombres premiers ?

Non.

Maintenant si on veut comparer les langages, passer 10s pour un truc qui peut se calculer entre 4 et 140ms à l'arrache (vu ta mémoire consommé, on est plutôt dans les 4ms de mon cas), c'est une absurdité au niveau d'un utilisateur mais aussi une absurdité énergétique.
On a dépensé environ plusieurs centaines fois plus d'énergie pour le même résultat, on s'étonne après de la consommation des ordinateurs dans le monde et du besoin d'acheter des tonnes RAM.

Donc tu mets 140ms et moi 1sec et cela représente des centaines de fois plus d'énergie ? C'est comme ton calcul plus haut, vraiment bizarre. Et surtout faux.

Ce qui n'est pas le sujet mais vu que tu t'es trompé massivement tout le long du fil, je comprends que tu cherches à noyer le poisson.
Au passage, tu ne sais vraiment pas comment tournent les vrais gros codes en Python et ce qui fait qu'on peut se permettre de les utiliser pour du calcul aussi intensif que l'IA ce qui rend tes remarques vraiment hors de propos.

[Archi3]

Maintenant, au niveau optimisation on peut faire mieux.
"x = x + 1" il serait mieux de mettre "x = x + 2" comme ça, on ne teste que les nombres impairs.

on peut même aller de 6 en 6 et ne tester que les 6n-1 et 6n+1 au-dessus de 2 et 3 (c'est un début d'implémentation du crible d'Erastothène)

[Garion]

Ce qui n'est pas le sujet mais vu que tu t'es trompé massivement tout le long du fil, je comprends que tu cherches à noyer le poisson.
Au passage, tu ne sais vraiment pas comment tournent les vrais gros codes en Python et ce qui fait qu'on peut se permettre de les utiliser pour du calcul aussi intensif que l'IA ce qui rend tes remarques vraiment hors de propos.

Attaque ad hominem, inacceptable pour moi dans toute discussion scientifique.
Fin de la discussion pour moi (malgré des arguments, je ne veux pas rentrer dans ce jeu puéril).