Algorithme sur les nombres premiers

matilda
Modifié (30 Oct) dans Arithmétique
Bonjour,
j'ai l'exercice suivant: Soit $n$ un entier $\geq 3.$
1- écrire un algorithme pour savoir si n est premier ou pas.
2- calculer le nombre d'entiers premiers inférieur à $M$ tel que $M$ est un entier donné.
En fait, je sais qu'un nombre premier est un nombre qui n'admet que deux diviseurs: 1 et lui même. Mais je bloque sur l'algorithme.
Merci d'avance pour votre aide.

Réponses

  • Pour la 1, il faut remplacer "entier ou pas", par "premier ou pas".
    C'est la suite de l'autre algorithme ? Si oui $R=0$ pour savoir un nombre en divise un autre.
    Comme me l'a appris ma maîtresse de CE2, tata Suzanne, dite Susu, $\{l,é,o\} \cap \{t,o,t,o\}=\{o\}$
  • Bonjour,
    1- Pour la question 1, voir si $n$ est premier ou pas, j'ai trouver comment faire.
    on fait une boucle sur $i$ et on divise $n$ par $i$.
    2- Pour la question 2, c'est un autre algo qu'l faut écrire. Je n'ai pas encore trouvé comment.
    Si quelqu'un a une idée, je vous remercie d'avance.
  • Fin de partie
    Modifié (30 Oct)
    Si tu as fait la question 1, la question 2 s'en déduit sans beaucoup effort. Je pense que tu bloques parce que tu ne visualises pas bien la question.

    Je te propose dans ta question 1 de transformer ton algorithme en fonction qui accepte en entrée un entier naturel strictement plus grand que $1$ et qui renvoie $1$ si le nombre est premier et $0$ autrement.
    Cela devrait t'aider pour écrire un algorithme très simple (peu performant mais qui fonctionne) pour la question 2.

    NB:
    Pour améliorer la rapidité de ton algorithme de la question 1, je te rappelle que si tu divises un nombre plus grand que $1$ par tous les entiers inférieurs à sa racine carrée (tu l'arrondis à l'unité inférieure si la racine carrée n'est pas un entier) et que le seul diviseur obtenu est $1$ alors ce nombre est premier.

    PS:
    Est-ce qu'un entier $n$ peut s'écrire comme $n=ab$ avec $a,b$ deux entiers strictement supérieurs  à la racine carrée de $n$? Si c'est le cas alors on a $\underbrace{ab}_{=n}> \underbrace{\sqrt{n}\sqrt{n}}_{=n}$ ce qui est absurde. Ce qui signifie que si $n$ n'est pas premier il a au moins un diviseur qui n'est pas $1$ et qui est inférieur ou égal à la racine carrée de $n$. S'il n'a pas un tel diviseur alors il est premier.
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • querty
    Modifié (30 Oct)
    Est-ce qu'un entier n peut s'écrire comme n=ab avec a,b deux entiers strictement supérieurs  à la racine carrée de n?

     Pour le démontrer, c'est très simple : il suffit de dire qu'un entier composé est un rectangle $(a \cdot b = n) $ de surface n.Ensuite, on transforme cette même surface en carré puis  conclure, ou, en gros, on

    $a \cdot b = n=\sqrt(n)^2\quad a\ne b$

     $a ---> \sqrt(n)$ 

      $b ---> \sqrt(n)$ 

     $a <\sqrt(n)\quad b> \sqrt(n) $ donc non il n'existe pas d'entier tel que ... ,Parce qu’un rectangle a toujours un côté plus petit qu’un carré de même surface.



  • @querty:  Je préfère "ma" démonstration dans le PS de mon précédent message.
    Si je voyais ce que tu écris dans une copie d'élève je ne serais pas convaincu par la démonstration: c'est fouillis et peu rigoureux.


    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • Comme tu veux, personnellement, transformer un rectangle en un carré de même surface suffit à le démontrer pour moi, 
    et c'est exactement ce que tu dis avec ton  $\underbrace{ab}_{=n}> \underbrace{\sqrt{n}\sqrt{n}}_{=n}$ sauf que pourquoi c'est absurde ???  mais entre nous .... hein
  • j'utilise le fait que si $a>a_1>0$ et $b>b_1>0$ alors on a $ab>a_1b_1$
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • matilda
    Modifié (30 Oct)
    Je suis perdue avec tous ces fils.
    Voici l'algorithme que j'ai fais pour voir si un nombre entier $n \geq 3$ est premier ou pas.
    Ici, Q est le nombre de diviseurs
    Début
    Entier n, i, Q
    Ecrire n
    Faire de i=1 à n avec un pas 1
    Si (n mod i = 0) alors 
                                     Q=Q+1
    Fin Si
    Sinon écrire Q
    Si (Q=2) alors n est premier
    Sinon n n'est pas premier
    Fin

    Question : Si on veut calculer le nombre de nombres premiers inférieurs à un entier $M$ donné. Dans ce cas, je ne sais pas comment modifier le premier algorithme pour obtenir ce nombre noté $l$.

    Merci d'avance pour votre aide.
  • Dès qu'un nombre est divisible par un nombre qui n'est ni $1$, ni lui-même, tu peux en conclure qu'il n'est pas premier donc on peut améliorer ton algorithme à peu de frais.
    Ton Q n'est pas initialisé, tu confonds lire et écrire. La saisie de $n$ se fait avec un "lire" j'imagine.

    Imagine que tu  veuilles compter le nombre de nombres premiers inférieurs ou égaux à un entier donné $M$.
    Tu prends $2$ tu vérifies s'il est premier et si c'est le cas tu fais une croix sur un bout de papier, tu passes à $3$, tu fais la même chose, et tu recommences jusqu'à ce que tu atteignes $M$, tu vérifies si $M$ est premier, s'il est premier tu fais une croix sur ton papier et tu t'arrêtes à $M$. Pour savoir combien il y a de nombres premiers inférieurs ou égaux à $M$ il te suffit de compter les croix écrites.



    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • lourrran
    Modifié (30 Oct)
    Tu cherches à créer un 'outil' (une boite noire, ou dans le jargon informatique, une fonction, ou une procédure). Tu pourras appeler cet outil et lui demander, cher outil XXX, dites moi si le nombre $1234567$ est premier ou pas. C'est la seule question à laquelle cet outil sait répondre, on a juste le choix du nombre $n$ à tester.
    Et l'outil te répondra de façon très basique : Oui (ce nombre est premier) , ou bien Non (ce nombre n'est pas premier). Dans les algorithmes, on n'emploie pas les mots clés Oui ou Non, mais Vrai ou Faux, c'est pareil.

    Donc ton outil va se présenter un peu comme ça : 

    Fonction Est_Premier(n) : 
       truc 
       si .... alors renvoyer Vrai  
       machin
       si ... alors renvoyer Faux
       // et à la fin, si les différents tests qu'on a fait n'ont rien donné, 
       //  on va bien répondre quelque chose à la personne qui nous appelle.
       Renvoyer Vrai   // réponse par défaut.
    Fin Fonction  Est_Premier

    Il peut y a différentes instructions , des boucles , des tests divers et varier (là où j'ai mis truc et machin) ; et surtout, il y a des Instructions Renvoyer pour envoyer notre réponse à la personne qui nous appelle.

    Et ce que FdP te dit, c'est que dès qu'on trouve au moins un diviseur pour notre nombre $n$, hop, on ne se prend pas la tête, on peut répondre aussitôt à la personne qui a appelé cette fonction : Non, ce nombre n'est pas premier. Pas la peine de chercher d'éventuels autres diviseurs.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
    L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara.
  • denise chemla
    Modifié (31 Oct)
    Bonsoir,
    Si je teste :
    $n = 50
    print(n)
    for i in range(1,n+1):
        if (n % i) == 0:
            q = q+1
        else:
            print(Q)
    if Q == 2:
        print(n,' est premier')
    else:
        print(n,' n est pas premier')

    $
    j'obtiens à l'exécution :



    Vous pouvez tester du python dans trinket ici

    ou bien dans Google colab, c'est chouette, on peut même programmer sur son téléphone (bon, l'écran est petit, c'est vrai).
    Cordialement,
    Denise Vella-Chemla
  • Une fois que sais déterminer automatiquement si un nombre est premier, le crible d'Ératosthène est un bon moyen pour compter les nombres premiers entre 2 et M.
  • Fin de partie
    Modifié (30 Oct)
    @philou22: Le crible d'Eratosthène ne détermine pas si un nombre est premier ou pas, comme son nom l'indique c'est un crible, il élimine tous les nombres qui ne sont pas premiers (parce qu'ils sont multiples d'un nombre plus grand que $1$) dans un intervalle donné.

    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • @Lourrran:  Je crains que le concept de fonction ne soit pas au programme des rudiments de programmation qui sont enseignés dans l'enseignement secondaire mais je peux me tromper (je n'ai jamais vu ce concept utilisé dans un exercice de bac)
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • philou22
    Modifié (30 Oct)
    Une fois que tu as un crible (en python une liste initialisée [1,1…,1] le premier 1 signifiant que 2 est premier, le dernier 1 que M est peut-être premier) avec barrés (mis à 0) suite à parcours de la liste, en faisant quelque chose s’il n’y a pas déjà 0, tous les nombres pas premiers inférieurs à M il est facile de compter les nombres premiers inférieurs à M en prenant la somme des valeurs de la liste. C’est moins coûteux que M tests de primalité ce qui est probablement ce qui est attendu au niveau de matilda.
  • Que veux-tu dire @Fin de partie ? Les fonctions en Python sont au programme, mais je n'ai peut-être pas compris.
    Comme me l'a appris ma maîtresse de CE2, tata Suzanne, dite Susu, $\{l,é,o\} \cap \{t,o,t,o\}=\{o\}$
  • @zeitnot:  Je ne vois que des exos d'initiation à la programmation qui sont uniformément les mêmes (seul l'habillage change) dans les copies de bacs blancs que je corrige à l'occasion et il n'y a pas la queue d'une fonction dedans.
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • Je ne comprends pas trop ce que tu dis, mais je suis claqué, je prends l'année complète 2023, il n'y a que ça  ?! Ou je ne comprends pas ce que tu entends par fonction.

    Comme me l'a appris ma maîtresse de CE2, tata Suzanne, dite Susu, $\{l,é,o\} \cap \{t,o,t,o\}=\{o\}$
  • Les fonctions python sont heureusement au programme dès la seconde. Par contre au collège avec Scratch il faut se contenter de « bloc fonctionnels » avec des paramètres en entrée mais pas de sortie ce qui peut être maladroitement contourné par l’affectation d’une variable globale en fin de bloc. 
  • Vu comment l'exercice est présenté, j'ai l'impression que ce qui est attendu, c'est un 'outil' pour dire si un nombre est premier. Puis utiliser cet outil N-1 fois pour tester tous les entiers inférieurs à N, pour compter combien sont premiers et combien sont composés. Ainsi, la question 2 est une suite logique de la question 1.
    Evidemment, en terme de rapidité, ce n'est pas terrible du tout, et un crible d'Eratosthène serait beaucoup plus efficace, mais je me dis que quand le formateur va corriger l'exercice, il proposera cette autre méthode.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
    L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara.
  • @zeitnot:  Tu as raison Il y a bien des fonctions dans des programmes en Python dans les sujets de bac donc cela me rassure l'indication que j'ai donnée plus haut à Matilda est pertinente dans le contexte. B)
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • @Matilda: Sais-tu ce qu'est une fonction en programmation?
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
  • zeitnot
    Modifié (30 Oct)
    Comme ici ?

    Edit : ok @Fin de partie , je tapais pendant que tu répondais.  :)
    Comme me l'a appris ma maîtresse de CE2, tata Suzanne, dite Susu, $\{l,é,o\} \cap \{t,o,t,o\}=\{o\}$
  • Bonsoir,

    Une erreur sur l'indentation du return ?

    Cordialement,
    Rescassol

  • philou22
    Modifié (30 Oct)
    M = int(input())
    print(sum(all(n%i for i in range(2, int(n**0.5)+1)) for n in range(2, M+1)))

  • yep, mal retapé sur l'APMEP.
    Comme me l'a appris ma maîtresse de CE2, tata Suzanne, dite Susu, $\{l,é,o\} \cap \{t,o,t,o\}=\{o\}$
  • philou22
    Modifié (30 Oct)
    def compter_premiers(M):
        if M < 2:
            return 0
        crible = [True] * (M + 1)
        crible[0:2] = [False, False]
        for p in range(2, int(M**0.5) + 1):
            if crible[p]:
                crible[p*p:M+1:p] = [False] * len(range(p*p, M+1, p))
        return sum(crible)
    M = int(input())
    print(compter_premiers(M))

  • denise chemla
    Modifié (31 Oct)
    Bonjour Matilda,
    J'ai corrigé ce que vous aviez peut-être à l'esprit hier :
    n = 10
    q2 = 0
    for k in range(1,n):
        q = 0
        for i in range(1,k+1):
            if (k % i) == 0:
                q = q+1
            #else:
            #    print(q)
        if q == 2:
            print(k,' est premier')
            q2 = q2+1
        else:
            print(k,' n est pas premier')
        print('q = ',q2)
    La variable q2 compte les premiers inférieurs à k tandis que la variable q compte les diviseurs (1 et k) de k et vaut 2 si k est premier. n est le plus grand nombre considéré. Il faut toujours bien se prendre la tête sur les bornes (un for python démarre à 0 et il faut utiliser un range (intervalle) qui contient comme borne sup la borne qui nous intéresse +1 (la borne sup n'est pas comprise) soit un for range k in (a,b): pour travailler sur tous les k de l'intervalle [a,b[ .
    Le # met les lignes qui alourdissaient tout en commentaire.
    Bonne suite !
    Cordialement,
    Denise

  • Bonjour,
    pour compter le nombre de nombres premiers inférieur à un entier $M$ donné.
    On vérifie chaque entier $p$ s'il est inférieur par $M$ puis on regarde s'il est premier.
    pourquoi on commence l'algorithme par $p=2?$ Pourquoi ne pas commencer par $p=1?$
    Merci d'avance
  • Car on sait que 1 n’est pas premier car il n’a pas exactement deux diviseurs positifs.
  • Fin de partie
    Modifié (31 Oct)
    @Matilda: Tu peux commencer par $1$ si tu veux puisque tu as l'air de vouloir compter le nombre de diviseurs des nombres et qu'un nombre est premier si et seulement si il a exactement deux diviseurs positifs distincts. (cela élimine $1$ qui n'a qu'un seul diviseur positif)

    Mais comme expliqué plus haut on n'a pas besoin de connaître le nombre total de diviseurs d'un nombre pour savoir si celui-ci* est composé, il suffit qu'on lui trouve un diviseur qui n'est ni $1$, ni lui-même pour conclure qu'il est composé et, par ailleurs, si un nombre n'a pas d'autre diviseur inférieur à sa racine carrée que $1$ alors il est premier.

    *: on ne doit considérer que des entiers $\geq 2$.
    Le passé est sinistre, le présent terne, mais heureusement nous n'avons pas d'avenir.
Connectez-vous ou Inscrivez-vous pour répondre.