Pourquoi vérifie-t-on jusqu'à la racine carrée d'un nombre premier pour déterminer s'il est premier ?

Question

Pour vérifier si un nombre est premier ou non, pourquoi devons-nous vérifier s'il est divisible uniquement jusqu'à la racine carrée de ce nombre ?

Answer 1

Soit n non premier. Par conséquent, il a au moins deux facteurs entiers supérieurs à 1. Soit f le plus petit de ces facteurs. Supposons que f > sqrt n. Alors n/f est un entier sqrt n, donc plus petit que f. Par conséquent, f ne peut pas être le plus petit facteur de n. Reductio ad absurdum ; le plus petit facteur de n doit être sqrt n.

Answer 2

Tout nombre composite est un produit de nombres premiers.

Disons que n = p1 * p2 où p2 > p1 et ils sont premiers.

Si n % p1 === 0 puis n est un nombre composite.

Si n % p2 === 0 alors devinez quoi n % p1 === 0 également !

Donc il n'y a aucune chance que si n % p2 === 0 pero n % p1 !== 0 en même temps. En d'autres termes, si un nombre composite n peut être divisé équitablement par p2,p3...pi (son facteur le plus élevé), il doit être divisé par son facteur le plus bas. p1 aussi. Il s'avère que le facteur le plus faible p1 <= Math.square(n) est toujours vrai.

Answer 3

Oui, comme cela a été correctement expliqué ci-dessus, il suffit d'itérer jusqu'à Math.floor de la racine carrée d'un nombre pour vérifier sa primalité (car sqrt couvre tous les cas possibles de division ; et Math.floor car tout nombre entier supérieur à sqrt sera déjà hors de sa portée).

Voici un extrait de code JavaScript exécutable qui représente une implémentation simple de cette approche - et sa "convivialité en temps d'exécution" est suffisante pour traiter des nombres assez grands (j'ai essayé de vérifier les nombres premiers et non premiers jusqu'à 10**12, c'est-à-dire 1 trillion, et j'ai comparé les résultats avec la fonction base de données en ligne des nombres premiers et je n'ai rencontré aucune erreur ou décalage, même sur mon téléphone bon marché) :

function isPrime(num) {
  if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) {
    return num === 2;
  } else {
    const sqrt = Math.floor(Math.sqrt(num));
    for (let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }
}

<label for="inp">Enter a number and click "Check!":</label><br>
<input type="number" id="inp"></input>
<button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

Answer 4

Pour tester la primalité d'un nombre, n on s'attendrait à une boucle telle que celle qui suit en premier lieu :

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

Ce que fait la boucle ci-dessus est le suivant : pour une donnée 1 < i < n il vérifie si n/i est un entier (en laissant le reste 0). S'il existe un i pour lequel n/i est un entier, alors on peut être sûr que n n'est pas un nombre premier, auquel cas la boucle se termine. Si pour aucun i, n/i est un entier, alors n est premier.

Comme pour chaque algorithme, nous demandons : Peut-on faire mieux ?

Voyons ce qui se passe dans la boucle ci-dessus.

La séquence de i va : i = 2, 3, 4, .... , n-1

Et la séquence de vérifications des entiers va : j = n/i, soit n/2, n/3, n/4, .... , n/(n-1)

Si pour un certain i = a, n/a est un nombre entier, alors n/a = k (nombre entier)

ou n = ak, clairement n > k > 1 (si k = 1, alors a = n, mais i n'atteint jamais n ; et si k = n, alors a = 1, mais i commence à former 2)

De plus, n/k = a, et comme indiqué ci-dessus, a est une valeur de i, donc n > a > 1.

Donc, a et k sont tous deux des entiers compris entre 1 et n (exclusif). Puisque i atteint chaque entier dans cet intervalle, à une certaine itération i = a, et à une autre itération i = k. Si le test de primalité de n échoue pour min(a,k), il échouera également pour max(a,k). Nous devons donc vérifier un seul de ces deux cas, à moins que min(a,k) = max(a,k) (où deux vérifications se réduisent à une seule), c'est-à-dire a = k, auquel cas a*a = n, ce qui implique a = sqrt(n).

En d'autres termes, si le test de primalité de n devait échouer pour un certain i >= sqrt(n) (c'est-à-dire max(a,k)), il échouerait également pour un certain i <= n (c'est-à-dire min(a,k)). Il suffirait donc d'exécuter le test pour i = 2 à sqrt(n).

Answer 5

def print_hi(n):
if(n == 1 ):
    return False;
if( n == 2 or n == 3):
    return True;
if(n % 2 == 0 or n % 3 == 0):
    return  False;

for i in range (5,n,6):
    if( i * i <= n):
        if(n % i == 0 or n % (i+2) == 0):
            return False
        return True

if __name__ == '__main__':
  x = print_hi(1032)
  print(x)