¿Por qué revisamos la raíz cuadrada de un número primo para determinar si es primo?

393

Para probar si un número es primo o no, ¿por qué tenemos que probar si es divisible solo hasta la raíz cuadrada de ese número?

Pan
fuente
33
porque si n = a*by a <= bentonces a*a <= a*b = n.
Will Ness
77
Para aclarar, esto significa que tenemos que probar solo hasta floor(sqrt(n)).
Acumenus

Respuestas:

660

Si un número nno es primo, se puede factorizar en dos factores ay b:

n = a * b

Ahora ay bno puede ser mayor que la raíz cuadrada de n, ya que el producto a * bsería mayor que sqrt(n) * sqrt(n) = n. Entonces, en cualquier factorización de n, al menos uno de los factores debe ser más pequeño que la raíz cuadrada de n, y si no podemos encontrar ningún factor menor o igual a la raíz cuadrada, ndebe ser primo.

Sven Marnach
fuente
¿Cómo sqrt(n)tiene que ser lo suficientemente preciso para que esta propiedad se mantenga dado que estamos usando puntos flotantes?
Benoît
@ Benoît Siempre puede usar el cheque en i * i <= nlugar de i <= sqrt(n)si desea evitar las complejidades de los números de punto flotante.
Sven Marnach
348

Digamos m = sqrt(n)entonces m × m = n. Ahora, si nno es primo, entonces nse puede escribir como n = a × b, entonces m × m = a × b. Tenga en cuenta que mes un número real n, mientras que , ay bson números naturales.

Ahora puede haber 3 casos:

  1. a> m ⇒ b <m
  2. a = m ⇒ b = m
  3. a <m ⇒ b> m

En los 3 casos, min(a, b) ≤ m. Por lo tanto, si buscamos hasta m, estamos obligados a encontrar al menos un factor de n, que es suficiente para mostrar que nno es primo.

BiGYaN
fuente
44
n = 12 m = sqrt (12) = 3.46, a = 2, b = 6. n = m m ie 12 = 3.46 * 3.46 y n = a b ie 12 = 2 * 6. Ahora, condición 3. a <m <b, es decir, 2 <3.46 <6. Por lo tanto, para verificar primos solo necesitamos verificar un número menor que 3.46, que es 2 para descubrir que ese número no es primo. Por lo tanto, verifique la divisibilidad por números menores o iguales a (si n = 4, m = a = b = 2) raíz cuadrada de n.
Anukalp
2
Creo que debemos resaltar la suposición primero. Suponga n is not a prime, y pruébelo, de lo contrario es primordial.
Huei Tan
En realidad, no estoy convencido de que sea una mejor respuesta. Es una respuesta correcta, pero en realidad no responde la pregunta. Simplemente describe algunas otras dinámicas alrededor de los números primos y el sqrt. Las respuestas de @ Sven son sucintas y no crean más preguntas en el proceso.
Jon M
1
Regresé a la última buena versión. te lo perdiste cuando alguien eliminó innecesariamente una palabra ('por lo tanto'), que es necesaria para el flujo.
Will Ness
55

Porque si un factor es mayor que la raíz cuadrada de n, el otro factor que se multiplicaría con él para igualar n es necesariamente menor que la raíz cuadrada de n.

patros
fuente
37

Una explicación más intuitiva sería: -

La raíz cuadrada de 100 es 10. Digamos axb = 100, para varios pares de ay b.

Si a == b, entonces son iguales y son la raíz cuadrada de 100, exactamente. Que es 10.

Si uno de ellos es menor que 10, el otro tiene que ser mayor. Por ejemplo, 5 x 20 == 100. Uno es mayor que 10, el otro es menor que 10.

Pensando en axb, si uno de ellos cae, el otro debe hacerse más grande para compensar, por lo que el producto permanece en 100. Giran alrededor de la raíz cuadrada.

La raíz cuadrada de 101 es aproximadamente 10.049875621. Entonces, si está probando el número 101 para primalidad, solo necesita probar los números enteros hasta el 10, incluido 10. Pero 8, 9 y 10 no son primos, por lo que solo tiene que probar hasta el 7, que es principal.

Porque si hay un par de factores con uno de los números mayores que 10, el otro tiene que ser menor que 10. Si el menor no existe, no hay un factor mayor de 101.

Si está probando 121, la raíz cuadrada es 11. Debe probar los enteros primos del 1 al 11 (inclusive) para ver si entra de manera uniforme. 11 entra 11 veces, entonces 121 no es primo. Si te hubieras detenido a las 10 y no hubieras probado 11, te habrías perdido 11.

Debe probar cada número entero primo mayor que 2, pero menor o igual que la raíz cuadrada, suponiendo que solo esté probando números impares.

``

Archit Garg
fuente
3
"Pensando en axb, si uno de ellos cae, el otro debe hacerse más grande para compensar, por lo que el producto permanece en 100. Giran alrededor de la raíz cuadrada". Mi aha momento! ¡Gracias!
Brian Wigginton
Esta es la mejor respuesta.
JeanieJ
19

Supongamos nque no es un número primo (mayor que 1). Entonces hay números ay btal que

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

Al multiplicar la relación a<=bpor ay bobtenemos:

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

Por lo tanto: (tenga en cuenta que n=ab)

a^2 <= n <= b^2

Por lo tanto: (Tenga en cuenta que ay bson positivos)

a <= sqrt(n) <= b

Entonces, si un número (mayor que 1) no es primo y probamos la divisibilidad hasta la raíz cuadrada del número, encontraremos uno de los factores.

LoMaPh
fuente
8

Supongamos que el entero dado Nno es primo,

Entonces N puede factorizarse en dos factores ay b, de 2 <= a, b < Ntal manera que N = a*b. Claramente, ambos no pueden ser mayores que sqrt(N)simultáneamente.

Supongamos sin pérdida de generalidad que aes menor.

Ahora, si no puede encontrar ningún divisor de Npertenencia en el rango [2, sqrt(N)], ¿qué significa eso?

Esto significa que Nno tiene ningún divisor en [2, a]as a <= sqrt(N).

Por lo tanto, a = 1y por lo b = ntanto, por definición, Nes primo .

...

Lectura adicional si no está satisfecho:

Muchas combinaciones diferentes de (a, b)pueden ser posibles. Digamos que son:

(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 ), ....., (a k , b k ). Sin pérdida de generalidad, asumir una i <b i , 1<= i <=k.

Ahora, para poder demostrar que Nno es primo, es suficiente demostrar que nada de un i puede factorizarse más. Y también sabemos que a i <= sqrt(N)y, por lo tanto, debe verificar hasta sqrt(N)que cubra todo a i . Y, por lo tanto, podrá concluir si Nes primo o no .

...


fuente
7

En realidad, se trata de usos básicos de factorización y raíces cuadradas.

Puede parecer abstracto, pero en realidad simplemente radica en el hecho de que el factorial máximo posible de un número no primo tendría que ser su raíz cuadrada porque:

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

Dado que, si algún número entero arriba 1y abajo o arriba se sqrroot(n)divide en partes iguales n, entonces nno puede ser un número primo.

Ejemplo de pseudocódigo:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}
Super gato
fuente
Observación brillante. Usando esta observación para crear una guarddeclaración en Swift junto con esta práctica stackoverflow.com/a/25555762/4475605 para hacer una salida anticipada de un cálculo en lugar de desperdiciar energía computacional. Gracias por tu publicación.
Adrian
@Adrian Debo confesar que después de volver a esta respuesta, encontré un error en el momento de su publicación. No puede realizar la división en un 0, y en teoría si pudiera ++iconvertirse en el número 1, que siempre devolvería falso (porque 1 se divide en todo). He corregido la respuesta anterior.
Super Cat
Sí ... Abordé eso en mi código ... su observación de raíz cuadrada es una excelente manera de arrojar un valor no primo antes de comenzar a ejecutar los cálculos. Me mataron en un gran número que resultó ser una gran pérdida de tiempo. También aprendí que este algoritmo también puede reducir sustancialmente los tiempos de procesamiento en grandes números. en.wikipedia.org/wiki/Miller –Rabin_primality_test
Adrian
6

Entonces, para verificar si un número N es primo o no. Solo necesitamos verificar si N es divisible por números <= SQROOT (N). Esto se debe a que si factorizamos N en 2 factores, digamos X e Y, es decir. N = X Y. Cada uno de X e Y no puede ser menor que SQROOT (N) porque entonces, X Y <N Cada uno de X e Y no puede ser mayor que SQROOT (N) porque entonces, X * Y> N

Por lo tanto, un factor debe ser menor o igual a SQROOT (N) (mientras que el otro factor es mayor o igual a SQROOT (N)). Entonces, para verificar si N es Prime solo necesitamos verificar esos números <= SQROOT (N).

rhea rodrigues
fuente
3

Digamos que tenemos un número "a", que no es primo [no significa número primo / compuesto - un número que puede dividirse equitativamente por números distintos de 1 o en sí mismo. Por ejemplo, 6 puede dividirse en partes iguales entre 2, o entre 3, así como entre 1 o 6].

6 = 1 × 6 o 6 = 2 × 3

Entonces, si "a" no es primo, entonces se puede dividir por otros dos números y digamos que esos números son "b" y "c". Lo que significa

a = b * c.

Ahora, si "b" o "c", cualquiera de ellos es mayor que la raíz cuadrada de "a" que la multiplicación de "b" y "c" será mayor que "a".

Entonces, "b" o "c" siempre es <= raíz cuadrada de "a" para probar la ecuación "a = b * c".

Debido a la razón anterior, cuando probamos si un número es primo o no, solo verificamos hasta la raíz cuadrada de ese número.

Abu Naser Md Shoaib
fuente
1
b & c <= Math.sqrt (n) ?; Debería ser más bien b || c (boc) ya que si n = 6, b = 3, c = 2, entonces Math.sqrt (n)> c.
daGo
Gracias amigo por la corrección. haciendo la corrección :)
Abu Naser Md Shoaib
2

Dado cualquier número n, entonces una forma de encontrar sus factores es obtener su raíz cuadrada p:

sqrt(n) = p

Por supuesto, si multiplicamos ppor sí mismos, entonces volvemos n:

p*p = n

Se puede reescribir como:

a*b = n

Donde p = a = b. Si aaumenta, entonces bdisminuye para mantener a*b = n. Por lo tanto, pes el límite superior.

Actualización: Hoy vuelvo a leer esta respuesta y me quedó más claro. El valor pno significa necesariamente un número entero porque si lo es, entonces nno sería un primo. Entonces, ppodría ser un número real (es decir, con fracciones). Y en lugar de pasar por todo el rango de n, ahora solo tenemos que pasar por todo el rango de p. La otra pes una copia espejo, por lo que en efecto reducimos a la mitad el rango. Y luego, ahora veo que podemos continuar rehaciendo square rooty haciéndolo phasta la mitad del rango.

truthadjustr
fuente
1

Sea n no primo. Por lo tanto, tiene al menos dos factores enteros mayores que 1. Sea f el menor de estos factores. Supongamos que f> sqrt n. Entonces n / f es un entero LTE sqrt n, por lo tanto más pequeño que f. Por lo tanto, f no puede ser el factor más pequeño de n. Reducción al absurdo; El factor más pequeño de n debe ser LTE sqrt n.

Cabaña Reb.
fuente
1

Cualquier número compuesto es un producto de primos.

Digamos n = p1 * p2, donde p2 > p1y son primos.

Si n % p1 === 0entonces n es un número compuesto.

Si n % p2 === 0entonces adivina qué n % p1 === 0también!

Así que no hay forma de que si, n % p2 === 0pero n % p1 !== 0al mismo tiempo. En otras palabras, si un número compuesto n puede dividirse equitativamente entre p2, p3 ... pi (su factor mayor), también debe dividirse por su factor más bajo p1 . Resulta que el factor más bajo p1 <= Math.square(n)siempre es cierto.

extranjero
fuente
Si tiene curiosidad por qué es cierto, @LoMaPh explicó el hecho en su respuesta en gran medida. Agregué mi respuesta porque tuve momentos realmente difíciles de visualizar y comprender otras respuestas proporcionadas. Simplemente no hizo clic.
daGo
0

Para probar la primalidad de un número, n , uno esperaría un ciclo como el siguiente en primer lugar:

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

Lo que hace el ciclo anterior es esto: para un determinado 1 <i <n , comprueba si n / i es un entero (deja el resto 0). Si existe una i para la cual n / i es un número entero, entonces podemos estar seguros de que n no es un número primo, momento en el cual termina el ciclo. Si para no i, n / i es un número entero, entonces n es primo.

Como con todos los algoritmos, preguntamos: ¿podemos hacerlo mejor?

Veamos qué está pasando en el bucle anterior.

La secuencia de i va: i = 2, 3, 4, ..., n-1

Y la secuencia de comprobaciones de enteros va: j = n / i, que es n / 2, n / 3, n / 4, ..., n / (n-1)

Si para algunos i = a, n / a es un número entero, entonces n / a = k (número entero)

o n = ak, claramente n> k> 1 (si k = 1, entonces a = n, pero nunca alcanzo n; y si k = n, entonces a = 1, pero comienzo la forma 2)

Además, n / k = a, y como se indicó anteriormente, a es un valor de i entonces n> a> 1.

Entonces, a y k son números enteros entre 1 yn (exclusivo). Como, alcanzo cada número entero en ese rango, en alguna iteración i = a, y en alguna otra iteración i = k. Si la prueba de primalidad de n falla para min (a, k), también fallará para max (a, k). Por lo tanto, debemos verificar solo uno de estos dos casos, a menos que min (a, k) = max (a, k) (donde dos controles se reducen a uno), es decir, a = k, en cuyo punto a * a = n, que implica a = sqrt (n).

En otras palabras, si la prueba de primalidad de n fallara para algunos i> = sqrt (n) (es decir, max (a, k)), entonces también fallaría para algunos i <= n (es decir, min (a , k)). Entonces, sería suficiente si ejecutamos la prueba para i = 2 a sqrt (n).

Aroonalok
fuente
Hay explicaciones mucho más cortas y en mi humilde opinión mucho más fáciles de entender y sobre el tema en los comentarios y las respuestas de 6 años ...
Thierry Lathuille