Pourquoi est-ce que nous vérifions à la racine carrée d'un nombre premier pour déterminer si elle est premier?

Question

Pour tester si un nombre est premier ou non, pourquoi nous devons tester si elle est divisible seulement jusqu'à la racine carrée de ce nombre?

Answer 1

Si un numéro n n'est pas premier, il peut être pris en deux facteurs a et b:

n = a * b

Si les deux a et b étaient supérieurs à la racine carrée de n, alors a * b serait supérieure à n. Donc, au moins un de ces facteurs doit être inférieur ou égal à la racine carrée de n, et si nous ne pouvons trouver aucun facteur inférieur ou égal à la racine carrée, n doit être premier.

Answer 2

Le m = sqrt(n) de dire Let m × m = n alors. Maintenant, si n est pas un premier n peut alors être écrit comme n = a × b, si m × m = a × b. Notez que m est un nombre réel alors que n, a et b sont des nombres naturels.

Maintenant, il peut y avoir 3 cas:

1. a> m ? b
2. a = b = m ? m
3. a m

Dans les 3 cas, min(a, b) ≤ m. Par conséquent, si nous cherchons à m, nous sommes obligés de trouver au moins un facteur de n, ce qui est suffisant pour montrer que n n'est pas premier.

Answer 3

Parce que si un facteur est supérieur à la racine carrée de n, l'autre facteur qui multiplierait avec elle à l'égalité n est nécessairement inférieure à la racine carrée de n.

Answer 4

Une explication plus intuitive serait la suivante: -

La racine carrée de 100 est 10. Soit par exemple de a x b = 100, pour diverses paires de a et b.

Si b ==, alors ils sont égaux, et sont la racine carrée de 100, exactement. Ce qui est 10.

Si l'un d'eux est inférieur à 10, l'autre doit être plus grande. Par exemple, 5 x 20 == 100. L'un est supérieur à 10, l'autre est inférieur à 10.

Penser à un x b, si l'un d'eux tombe en panne, l'autre doit grossir pour compenser, de sorte que les séjours de produits à 100. Ils pivotent autour de la racine carrée.

La racine carrée de 101 est sur le point 10,049875621. Donc, si vous testez le numéro 101 pour primalité, il vous suffit d'essayer les entiers à travers 10, y compris 10. Mais 8, 9 et 10 ne sont pas eux-mêmes le premier, donc vous suffit de tester à travers 7, qui est premier.

Parce que s'il y a une paire de facteurs avec l'un des plus grands nombres de 10, l'autre de la paire doit être inférieur à 10. Si le plus petit n'existe pas, il n'y a pas plus grand facteur correspondant de 101.

Si vous testez 121, la racine carrée est 11. Vous devez tester les premiers entiers 1 à voir si elle va dans uniformément 11 (inclus). 11 va en 11 fois, donc 121 n'est pas premier. Si vous aviez arrêté à 10, et non testé 11, vous auriez manqué 11.

Vous devez tester tous les plus premier entier de 2, mais inférieure ou égale à la racine carrée, en supposant que vous testez uniquement des nombres impairs.

`

Answer 5

Supposons n est pas un nombre premier (de supérieur à 1). Donc, il y a un nombre a et b tels que

n = ab      (1 < a <= b < n)

En multipliant la relation a<=b par a et b nous obtenons:

a^2 <= ab
 ab <= b^2

Par conséquent: (notez que n=ab)

a^2 <= n <= b^2

Par conséquent: (Notez que a et b sont positifs)

a <= sqrt(n) <= b

Donc, si un certain nombre (supérieur à 1) n'est pas premier et nous divisibilité de test jusqu'à la racine carrée du nombre, nous trouverons un des facteurs.

Answer 6

Il est vraiment juste toutes les utilisations de base de racines et factorisation Square.

Il peut sembler être abstraite, mais en réalité simplement réside dans le fait qu'un non-prime-nombre maximal factoriel possible de devrait être sa racine carrée parce que:

sqrroot(n) * sqrroot(n) = n .

Étant donné que, si un nombre entier ci-dessus 1 et au-dessous ou jusqu'à sqrroot(n) se divise uniformément dans n , puis n ne peut pas être un nombre premier.

exemple de pseudo-code suivant:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

Answer 7

Supposons que le N entier donné n'est pas premier,

Alors N peut être factorise en deux facteurs a et b, 2 <= a, b < N telle que N = a*b. De toute évidence, les deux d'entre eux ne peut être supérieure à sqrt(N) simultanément.

Supposons sans perte de généralité que a est plus petite.

Maintenant, si vous ne pouviez pas trouver un diviseur de N appartenance à la gamme [2, sqrt(N)], qu'est-ce que ça veut dire?

Cela signifie que N ne propose pas de diviseur dans [2, a] comme a <= sqrt(N).

Par conséquent, a = 1 et b = n et donc Par définition, N est premier .

...

Pour en savoir plus si vous n'êtes pas satisfait:

De nombreuses combinaisons de (a, b) peuvent être possibles. Disons qu'ils sont:

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a < sub> 3 , b ₃ ), ....., (a _k , b _k ). Sans perte de généralité, supposons un _i i , 1<= i <=k.

Maintenant, pour être en mesure de montrer que N n'est pas premier, il suffit de montrer qu'aucun d'un _i peut être décomposées plus loin. Et nous savons aussi qu'un _i <= sqrt(N) et donc vous devez vérifier jusqu'à ce sqrt(N) qui couvrira tout un _i . Et par conséquent, vous serez en mesure de conclure si oui ou non N est premier.

...

Answer 8

Donc, pour vérifier si un nombre N est premier ou non. Nous devons vérifier que si N est divisible par le nombre <= SQROOT (N). En effet, si l'on tient compte N dans les 2 facteurs dire X et Y, par exemple. N = X Y. Chacun de X et Y ne peut pas être inférieure à SQROOT (N) car alors, X Y N

Par conséquent, un facteur doit être inférieur ou égal à SQROOT (N) (tandis que l'autre facteur est supérieur ou égal à SQROOT (N)). Donc, pour vérifier si N est premier, nous vérifions les besoin que d'un nombre <= SQROOT (N).

Answer 9

Soit s dire que nous avons un certain nombre « un », ce qui est premier [pas de moyens de nombres premiers / composites - un nombre qui peut être divisé à parts égales par des numéros autres que 1 ou lui-même. Par exemple, 6 peut être divisé de façon égale par deux ou par trois, ainsi que par 1 ou 6].

6 = 1 × 6 ou 6 = 2 x 3

Alors maintenant, si « un » est pas premier alors il peut être divisé par deux autres chiffres et nous allons dire que ces chiffres sont « b » et « c ». Ce qui signifie

a = b * c.

Maintenant, si « b » ou « c », l'un d'eux est plus grande que la racine carrée « une » que la multiplication des « b » et « c » sera supérieure à « un ».

Alors, "b" et "c" est toujours <= racine carrée de "a" pour prouver l'équation "a = b * c".

En raison de la raison ci-dessus, lorsque nous testons si un nombre est premier ou non, nous vérifions seulement jusqu'à la racine carrée de ce nombre.

Answer 10

Soit n non premier. Par conséquent, il a au moins deux facteurs de nombre entier supérieur à 1. Soit f le plus petit de ces facteurs de n. Supposons que f> sqrt n. Puis n / f est un sqrt LTE entier n, donc inférieure à f. Par conséquent, f ne peut pas être plus petit facteur de n. Absurdum ad reductio; le plus petit facteur de n doit être le n LTE.

Answer 11

Étant donné un nombre n, puis un moyen de trouver ses facteurs est d'obtenir sa racine carrée p:

sqrt(n) = p

Bien sûr, si l'on p multiplier par lui-même, nous obtenons n retour:

p*p = n

Il peut être réécrite comme:

a*b = n

Où p = a = b. Si l'augmentation de a, puis b diminue pour maintenir a*b = n. , p est donc la limite supérieure.

Answer 12

Pour tester la primalité d'un nombre, n , on pourrait attendre d'une boucle, comme suit, en premier lieu:

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

Ce que la boucle ci-dessus fait est la suivante: pour une donnée 1 , il vérifie si n / i est un nombre entier (feuilles reste 0). S'il existe un i pour lequel n / i est un entier, alors nous pouvons être sûrs que n est pas un nombre premier, à quel point la boucle se termine. Si sans i, n / i est un entier, alors n est premier.

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

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

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

Et la séquence de contrôles entier va: j = n / i, ce qui est n / 2, n / 3, n / 4, ..., n / (n-1)

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

ou n = ak, clairement n> k> 1 (si k = 1, a = n, mais je ne parvient jamais n, et si k = n, alors a = 1, mais i commence forme 2)

En outre, n / k = a, et comme indiqué ci-dessus, a est une valeur de i si n> a> 1.

, a et k sont les deux nombres entiers compris entre 1 et n (exclusif). Depuis, j'atteint tout entier dans cette plage, à une itération i = a, et à une autre itération i = k. Si le test de primalité de n échoue pour min (a, k), il sera également échouer pour max (a, k). Nous avons donc besoin de vérifier que l'un de ces deux cas, à moins que min (a, k) = max (a, k) (où deux contrôles réduisent à un) par exemple, a = k, à quel point a * a = n, implique a = sqrt (n).

En d'autres termes, si le test de primalité de n échouait pour certains i> = sqrt (n) (c.-à-max (a, k)), il échouerait aussi pour un certain i <= n (ie, min (a, k)). Ainsi, il suffirait que nous courons le test i = 2 à sqrt (n).

Answer 13

Tout nombre composite est un produit de nombres premiers.

Disons n = p1 * p2, où p2 > p1 et ils sont les nombres premiers.

Si n % p1 === 0 puis n est un nombre composé.

Si n % p2 === 0 puis devinez quoi n % p1 === 0 aussi bien!

Il n'y a donc aucun moyen que si n % p2 === 0 mais n % p1 !== 0 en même temps. En d'autres termes, si un nombre composé n peut être divisé à parts égales par p2, p3 ... pi (son facteur de plus), il doit être divisé par le facteur le plus bas p1 aussi. Il se trouve que le plus bas p1 <= Math.square(n) facteur est toujours vrai.