avis , nombre premier calculator

bonjour, j’ai code qui check si n est nombre premier et je voudrai votre avie pour ce code et comment l’optimiser au max (je l’ai fait en oneliner et en normal, mais mon code est loin d’etre parfait ) donc 1 version

def check_prime_number(n: int) -> bool:
  '''check if n is a prime number'''
  list_mod = [] 
  for i in range(2, n):
    list_mod.append(n%i) 
  return all(list_mod)

donc la 2v en oneliner:

f = lambda n: all(n%i for i in range(2, n))

merci pour votre commentaire

Salut,

Il y a plusieurs optimisations que tu peux faire ici :

• Pour commencer, tu génères actuellement une liste pour chaque nombre entre 2 et n, ce qui, pour les très grands nombres, fera vite exploser la quantité de mémoire utilisée.

  Pour y remédier, tu peux effectuer à la place un simple test if sur le modulo n % i dans ta boucle for, afin de vérifier si n est divisible par n ou non.

• Une fois cette première étape faite, tu devrais t’être retrouvé avec un booléen valant True à la fin de ta boucle si le nombre est premier, ou False s’il ne l’est pas. Tu peux alors optimiser le temps d’exécution ! En effet, si au cours de ta boucle, tu tombes sur un cas de nombre i qui divise bien n, alors tu sais déjà que ton nombre ne sera pas premier (c’est un contre-exemple)… et tu peux donc immédiatement retourner False, ce qui arrêtera ta boucle ! Conséquence directe : si ta boucle se termine jusqu’à la fin, alors tu sais que ton nombre est premier, et tu peux retourner True, sans faire le moindre if

Salut,

À noter que les optimisations proposées par @Deuchnord sont en fait déjà là dans ta version one liner parce que tu donnes un générateur à all plutôt qu’une liste. Un one liner réellement équivalent à ta fonction (et donc mauvais) serait lambda n: all([n%i for i in range(2, n)]) pour construire une liste avec les modulos.

Une autre optimisation est que tu peux t’arrêter à $\lfloor\sqrt n\rfloor$ (partie entière de $\sqrt n$) puisque aucun nombre dans $(\lfloor\sqrt n\rfloor, n)$ ne va diviser $n$. Tu peux aussi ne tester que les nombres impairs de $[3, \lfloor\sqrt n\rfloor]$ après avoir testé $2$. Ou même raffiner encore un peu et faire un filtre d’Ératosthène sur $[2, \lfloor\sqrt n\rfloor]$ pour ne tester les divisibilités que sur les nombres premiers dans cet intervalle (ce qui n’est probablement rentable qu’à partir d’un certain $n$).

et bah merci @adri1 et @deuchnord je vais regarder vos messages

donc

f = lambda n: all(n%i for i in range(2, round(math.sqrt(n))))

parce que math.sqrt donne un nombre flottant donc il faut l’arrondir

int(sqrt(n))+1 plutôt pour avoir l’entier arrondi à l’inférieur, et +1 (comme range exclut la borne supérieur) parce qu’il faut inclure $\lfloor\sqrt n\rfloor$ dans la recherche (sinon tu vas avoir un problème avec les carrés).

ok merci donc

_ = lambda n: all(n%i for i in range(2, int(math.sqrt(n))+1))

bon maintenant il faut calculer la racine carre sans utilise math.sqrt

f = lambda n: all(n%i for i in range(2, int(math.sqrt(n))+1))

C’est correct, mais pourquoi en faire une lambda mais la nommer quand même ? Si tu vas la nommer, autant en faire une vraie fonction avec une docstring et tout. Ça va aussi rendre d’autres optimisations plus facile, comme l’exclusion des nombres pairs après avoir testé 2.

Pourquoi ? Il suffit de prendre n**0.5, mais quel est le but d’éviter un import qui ne fera que rendre ton code plus lisible ? C’est pour du code golf ? Si oui, t’as pas besoin d’être optimal, et Python n’est peut être pas le meilleur choix.

EDIT : en fait, je viens de réaliser que le test n’est pas correct pour n == 0 et n == 1. Il renvoie True alors que ces nombres ne sont pas premiers comme le range est vide.

EDIT : en fait, je viens de réaliser que le test n’est pas correct pour n == 0 et n == 1. Il renvoie True alors que ces nombres ne sont pas premiers comme le range est vide.

Tiens, je pense que le plus simple est de vérifier que le nombre est > 1 avant tout. Il ne me semble pas correcte non plus pour des valeurs < 0.

On peut aussi dire qu’on s’en fout des nombres négatifs comme ça devrait être le boulot du système de type de récupérer que des nombres positifs (après tout, la fonction va renvoyer n’importe quoi si on lui file un flottant comme le typage de Python est troué). Le test n > 1 est cela dit celui que j’ai adopté en faisant le golf en Rust (28 caractères! Je pensais pas pouvoir faire aussi largement mieux que Python avec la même idée).

À la lecture de tes messages @NightProg j’ai l’impression que tu mélanges plusieurs réalités derrière le mot « optimisation ». En particulier, tu sembles essayer de faire un code compact et rapide, ce qui n’est pas toujours facile. Beaucoup d’optimisations sur un point nécessitent de faire des sacrifices sur d’autres : un code compact sera rarement le plus rapide ; un code rapide pourra consommer beaucoup de mémoire ; un code économe en mémoire sera rarement le plus rapide ; un code rapide ou économe en mémoire demandera souvent d’écrire plus de lignes de code qu’une version compacte, etc.

(C’est une règle générale, on peut trouver des contre-exemples à tous les cas).

PS : et souvent, optimiser un code (pour quelque métrique que ce soit) impose de sacrifier sa lisibilité.

Pour renchérir sur ce que dis SpaceFox, tu devrais aussi mesurer la performance de ton code, pour vérifier, qu’effectivement il est plus rapide (ou plus économe en mémoire, par exemple).

Tu pourrais aussi rajouter des tests pour s’assurer de sa justesse aussi, vu qu’un algo rapide qui rend le mauvais résultat ne vaut rien.