Trouver un nombre premier?

N est premier s’il s’agit d’un entier positif divisible par exactement deux entiers positifs, 1 et N. Etant donné que les diviseurs d’un nombre ne peuvent pas être plus grands que ce nombre, cela donne lieu à un simple test de primalité:

• Si un nombre entier N supérieur à 1 n’est divisible par aucun nombre entier compris dans l’intervalle [2, N-1] , alors N est premier. Sinon, N n’est pas premier.

Cependant, il serait intéressant de modifier ce test pour le rendre plus rapide. Alors laissez-nous enquêter.

Notez que les diviseurs de N apparaissent par paires. Si N est divisible par un nombre M, il est également divisible par N / M. Par exemple, 12 est divisible par 6, et donc par 2. De plus, si M >= sqrt(N) , alors N/M <= sqrt(N) .

Cela signifie que si aucun nombre inférieur ou égal à sqrt (N) ne divise N, aucun nombre supérieur à sqrt (N) ne divise N non plus (à l'exception de 1 et N eux-mêmes), sinon une contradiction se produirait.

Nous avons donc un meilleur test:

• Si un nombre entier N supérieur à 1 n'est divisible par aucun nombre entier compris dans l'intervalle [2, sqrt(N)] , alors N est premier. Sinon, N n'est pas premier.

Si vous considérez le raisonnement ci-dessus, vous devriez voir qu'un nombre qui réussit ce test réussit également le premier test et un nombre qui échoue à ce test échoue également au premier test. Les tests sont donc équivalents.

Un nombre composé (un qui n’est pas premier ou 1) a au moins 1 paire de facteurs et il est garanti qu’un des nombres de chaque paire est inférieur ou égal à la racine carrée du nombre (qui est ce que vous demandent à propos de).

Si vous carréz la racine carrée du nombre, vous obtenez le nombre lui-même ( sqrt(n) * sqrt(n) = n ), donc si vous faites l’un des nombres plus grand (que sqrt(n) ), vous devrez faire l’autre plus petit. Si vous ne cochez que les nombres 2 à sqrt(n) vous aurez coché tous les facteurs possibles, car chacun de ces facteurs sera associé à un nombre supérieur à sqrt(n) (sauf bien sûr si le nombre est En fait, un carré d’un autre nombre, comme 4, 9, 16, etc., mais cela n’a pas d’importance, car vous savez qu’ils ne sont pas premiers;

La raison est simple: tout nombre supérieur au carré entraînera la multiplication de l’autre multiplicateur, qui sera inférieur au carré. Dans ce cas, vous devriez déjà l’avoir vérifié.

Soit n = a × b un composé.

Supposons a > sqrt ( n ) et b > sqrt ( n ).

a × b > sqrt ( n ) × sqrt ( n )

a × b > n

Mais nous connaissons a × b = n , donc a n ) ou b n ).

Etant donné que vous devez uniquement connaître a ou b pour indiquer que n est composite, il vous suffit de vérifier les nombres allant jusqu’à sqrt ( n ) pour le trouver.

Parce que dans le pire des cas, le nombre n peut être exprimé sous la forme d’un ² .

Si le nombre peut être exprimé différemment, que l’un des diviseurs sera inférieur à a = sqrt(n) , mais l’autre peut être plus grand.