Nombres premiers

Posté par rad rad

Bonsoir,
je ne suis pas trop à l'aise avec l'informatique et je n'arrive pas à ecrire la fonction estPremier(n) qui prend un entier n (n ou = 2) en argument, et qui renvoie 1 si n est premier et 0 sinon.

J'ai pensé à utilisé un boucle if mais bon je galere depuis maintenant plus d'une heure sans résultat donc j'en demande à votre aide.

Merci d'avance et bonne soirée

Posté par rad rad

erratum : le fonction estPremier(n) qui prend un entier n (n > ou = 2) en argument
je vous prie de bien vouloir m'excusez

Posté par Bachstelze Bachstelze

Bonjour

Solution naïve en PYthon, à adapter :

def est_premier(n):
    for i in range(2,n):
        if n%i == 0:
            return True
    return False

Ceci sera évidemment très lent si n est grand, il y a énormément de possibilités d'amélioration.

Posté par Asap Asap

D'accord avec la solution de Bachstelze, tu peux légèrement améliorer la rapidité d'exécution en bouclant jusqu'a la partie entiere de n/2 au lieu de n (soit n/2 si n est pair, (n-1)/2 si n est impair), étant donné qu'aucun nombre supérieur à n/2 ne peut être un diviseur de n. (tu peux facilement le vérifier)

Posté par Camélia Camélia

Bonjour

On peut faire encore (un peu) mieux... Onn peut s'arrêter à partie entière de

Posté par carpediem carpediem

salut

.... et encore mieux en ne prenant que 2 et les impairs E(n) ....

Posté par Camélia Camélia

... et en faisant un crible, on ne prend plus que les premiers inférieurs à

Posté par carpediem carpediem

oui mais alors si on a les premiers pourquoi chercher les premiers !!!!

Posté par rad rad

Merci à tous pour vos réponses et bonne soirée