algorithm - saber - ¿Por qué comprobamos hasta la raíz cuadrada de un número primo para determinar si es primo?
raiz cuadrada de un numero primo es irracional (12)
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?
Así que para comprobar si un número N es Prime o no. Solo debemos comprobar si N es divisible por números <= SQROOT (N). Esto se debe a que, si factorizamos N en cualquiera de los 2 factores, decimos 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).
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 p por sí mismo, entonces recuperamos n :
p*p = n
Se puede reescribir como:
a*b = n
Donde p = a = b . Si a aumenta, entonces b disminuye para mantener a*b = n . Por lo tanto, p es el límite superior.
Digamos que m = sqrt(n) entonces m × m = n . Ahora bien, si n no es un número primo, entonces n puede escribirse como n = a × b , entonces m × m = a × b . Observe que m es un número real, mientras que n , a y b son números naturales.
Ahora puede haber 3 casos:
- a> m ⇒ b <m
- a = m ⇒ b = m
- 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 n no es primo.
Digamos que tenemos un número "a", que no es primo [no significa número primo / compuesto ”, un número que se puede dividir en partes iguales por números distintos de 1 o de sí mismo. Por ejemplo, 6 puede dividirse uniformemente por 2, o por 3, así como por 1 o 6].
6 = 1 × 6 o 6 = 2 × 3
Entonces, si "a" no es primo, 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" y "c" es siempre <= 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.
En realidad, todos son usos básicos de la factorización y las 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 un número entero por encima de 1 y por debajo o hasta sqrroot(n) divide uniformemente en n , n no 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;
}
Para probar la primalidad de un número, n , uno esperaría un bucle 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 bucle anterior es esto: para un 1 <i <n dado, comprueba si n / i es un número 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, en cuyo punto termina el bucle. Si para no i, n / i es un entero, entonces n es primo.
Al igual que con cada algoritmo, preguntamos: ¿Podemos hacerlo mejor?
Veamos lo que está pasando en el bucle anterior.
La secuencia de i va: i = 2, 3, 4, ..., n-1
Y la secuencia de verificaciones 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 entero, entonces n / a = k (entero)
o n = ak, claramente n> k> 1 (si k = 1, entonces a = n, pero nunca llego a n; y si k = n, entonces a = 1, pero i comienza con 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 ambos enteros entre 1 y n (exclusivo). Como, alcanzo todos los enteros en ese rango, en alguna iteración i = a, y en 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 cheques 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)). Por lo tanto, sería suficiente si ejecutamos la prueba para i = 2 a sqrt (n).
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.
Sea n no primo. Por lo tanto, tiene al menos dos factores enteros mayores que 1. Sea f el más pequeño de n tales factores. Supongamos que f> sqrt n. Entonces n / f es un entero LTE sqrt n, por lo tanto menor 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.
Si un número n no es un número primo, puede dividirse en dos factores a y b :
n = a*b
Si tanto a como b fueran mayores que la raíz cuadrada de n , a*b sería mayor que n . Entonces, al menos uno de esos factores debe ser menor o igual que la raíz cuadrada de n , y para verificar si n es primo, solo necesitamos probar los factores menores o iguales a la raíz cuadrada.
Supongamos que n no es un número primo (mayor que 1). Así que hay números b tales que
n = ab (1 < a <= b < n)
Al multiplicar la relación a<=b por a y b obtenemos:
a^2 <= ab
ab <= b^2
Por lo tanto: (note que n=ab )
a^2 <= n <= b^2
Por lo tanto: (Tenga en cuenta que a y b son 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.
Supongamos que el entero N dado no es primo,
Luego, N puede ser factorizado en dos factores a y b , 2 <= a, b < N , de manera que N = a*b . Claramente, ambos no pueden ser mayores que sqrt(N) simultáneamente.
Supongamos sin pérdida de generalidad que a es menor.
Ahora, si no pudo encontrar ningún divisor de N perteneciente al rango [2, sqrt(N)] , ¿qué significa eso?
Esto significa que N no tiene ningún divisor en [2, a] como a <= sqrt(N) .
Por lo tanto, a = 1 y b = n y, por lo tanto, por definición, N es 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, suponga que i <b i , 1<= i <=k .
Ahora, para poder demostrar que N no es primo, es suficiente para demostrar que ninguno de i puede ser factorizado aún más. Y también sabemos que a i <= sqrt(N) y, por lo tanto, debe verificar hasta sqrt(N) que cubrirá toda una i . Y por lo tanto, podrás concluir si N es primo o no.
...
Una explicación más intuitiva sería: -
La raíz cuadrada de 100 es 10. Digamos que axb = 100, para varios pares de a y b.
Si a == b, entonces son iguales, y son exactamente la raíz cuadrada de 100. Que es el 10
Si uno de ellos es menor que 10, el otro debe 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 baja, el otro debe crecer más para compensar, por lo que el producto se mantiene 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 la primalidad, solo necesita probar los números enteros hasta 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 par debe ser menor que 10. Si el más pequeño no existe, no hay un factor mayor que coincida con 101.
Si está probando 121, la raíz cuadrada es 11. Tiene que probar los enteros primos del 1 al 11 (inclusive) para ver si entran de manera uniforme. 11 va en 11 veces, por lo que 121 no es primo. Si se hubiera detenido a las 10 y no se hubiera probado el 11, habría perdido 11.
Debe probar cada entero primo mayor que 2, pero menor o igual que la raíz cuadrada, suponiendo que solo está probando números impares.
`