Trouver 2 nombres premiers entre 300 et 400?
Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Trouver 2 nombres premiers entre 300 et 400?



  1. #1
    invite21fd11b1

    Trouver 2 nombres premiers entre 300 et 400?


    ------

    Bonjour

    Dans un exo, il faut que je trouve 2 nombres premiers entre 300 et 400.
    Je voulais savoir si il existait une autre mehtode, plus sure et plus rapide, que de faire un tableau ou j'écris ts les nbrs et ou je barre les multiples de 5, 10, 2, etc...?

    Merci

    -----

  2. #2
    invite8a003157

    Re : Trouver 2 nombres premiers entre 300 et 400?

    1ère méthode: Produire le tableau dont tu parles (crible d'Ératosthène). Il n'est pas nécessaire de commencer à partir de 1. Choisir un intervalle de largeur raisonnable. Attention, la fréquence des nombres premiers diminue quand on va vers des grands nombres. Essayer par exemple avec [301..320].

    2è méthode: Tester les premiers candidats possibles à partir de 300: 301, 307, 311, 313, 317, etc. Les nombres intermédiaires sont exclus d'office: ils sont visiblement pairs, multiples de 3 ou de 5.
    Indication supplémentaire: On note V pour racine carrée. Un nombre inférieur à 400 qui n'est pas premier a obligatoirement un diviseur inférieur à 20 = V400. En effet, si l'on écrit n = a*b, avec a >= Vn, alors b <= n/Vn = Vn. Il faut donc tester la divisibilité (à la calculatrice) par tous les nombres premiers compris entre 7 et 20. On a vite fait le tour: 7, 11, 13, 17 et 19.

  3. #3
    invite8a003157

    Re : Trouver 2 nombres premiers entre 300 et 400?

    Pour information:
    En cryptographie (domaine de l'arithmétique qui s'occupe des problèmes liés au cryptage et à la sécurité des données), on a parfois besoin de savoir générer des très grands nombres premiers aléatoires. Pour cela, on choisit un grand nombre au hasard, et on teste s'il est premier. S'il ne l'est pas, on recommence jusqu'à ce qu'on en trouve un. Le problème, c'est, comme tu as pu le constaté, que le test simple (divisibilité par tous les nombres premiers jusqu'à Vn) peut nécessiter énormément de calculs dès que n est grand, et ce même pour un ordinateur. Pour y arriver, on a mis au point d'autres tests, beaucoup plus rapides, mais probabilistes: on n'est pas certain que le résultat qu'il donne soit juste. Il faut donc le répéter un certain nombre de fois pour être suffisamment sûr. Le plus simple d'entre eux s'appuie sur le petit théorème de Fermat. Tu trouveras sans doute plus d'informations à ce sujet sur Wikipédia, si ça t'intéresse. Attention, ça demande un certain niveau en maths.

Discussions similaires

  1. Deux nombres premiers entre eux
    Par invite425270e0 dans le forum Mathématiques du collège et du lycée
    Réponses: 22
    Dernier message: 09/12/2007, 18h22
  2. nombres premiers entre eux
    Par inviteae9ea1cc dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 14/10/2007, 19h45
  3. Nombres premiers entre eux
    Par invite41f753b8 dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 15/03/2007, 01h07
  4. [exo] Nombres Premiers entre eux.
    Par invite9b6e0fb5 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 02/01/2006, 10h48