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

Question

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?

Answer 1

Si un número n no es un mejor, se puede tener en cuenta en dos factores a y b:

n = a * b

Si ambos a y b eran mayores que la raíz cuadrada de n, después a * b sería mayor que n. Entonces, al menos uno de esos factores debe ser menor o igual a la raíz cuadrada de n, y si no podemos encontrar ningún factor menor o igual a la raíz cuadrada, n Debe ser primo.

Answer 2

Digamos m = sqrt(n) después m × m = n. Ahora si n no es un mejor entonces n Se puede escribir como n = a × b, asi que m × m = a × b. Darse cuenta de m es un número real mientras n, a y b son 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, seguramente encontraremos al menos un factor de n, que es suficiente para mostrar que n no es primo.

Answer 3

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

Answer 4

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

La raíz cuadrada de 100 es 10. Digamos AXB = 100, para varios pares de A y B.

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

Si uno de ellos es inferior a 10, el otro tiene que ser mayor. Por ejemplo, 5 x 20 == 100. Uno es mayor que 10, el otro es inferior a 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. Pivote alrededor de la raíz cuadrada.

La raíz cuadrada de 101 es de aproximadamente 10.049875621. Entonces, si está probando el número 101 para la Primalidad, solo necesita probar los enteros hasta 10, incluidos 10. Pero 8, 9 y 10 no son en sí mismos, por lo que solo tiene que probar hasta las 7, que es principal.

Porque si hay un par de factores con uno de los números mayores que 10, el otro del par debe ser inferior a 10. Si el más pequeño no existe, no hay un factor más grande de 101.

Si está probando 121, la raíz cuadrada es 11. Debe probar los Integers Prime 1 a 11 (inclusive) para ver si entra de manera uniforme. 11 entra 11 veces, por lo que 121 no es primo. Si se hubiera detenido a las 10 y no haya probado 11, se habría perdido 11.

Debe probar cada entero principal mayor de 2, pero menor o igual a la raíz cuadrada, suponiendo que solo está probando números impares.

`

Answer 5

Suponer n no es un número primo (mayor que 1). Entonces hay números a y b tal que

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

Multiplicando la relación a<=b por a y b obtenemos:

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 a y b son positivos)

a <= sqrt(n) <= b

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

Answer 6

Todo es realmente solo usos básicos de factorización y raíces cuadradas.

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

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

Dado eso, si hay un número completo de arriba 1 y debajo o hasta sqrroot(n) se divide uniformemente en n, después 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;
}

Answer 7

Supongamos que el entero dado N no es primo

Entonces n se puede factorizar en dos factores a y b , 2 <= a, b < N tal que N = a*b. Claramente, ambos no pueden ser mayores que sqrt(N) simultaneamente.

Supongamos sin pérdida de generalidad que a es más pequeño.

Ahora, si no pudieras encontrar ningún divisor de N perteneciente a la gama [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) puede ser posible. Digamos que son:

(a₁, b₁), (a₂, b₂), (a₃, b₃), ..... , (a_k, b_k). Sin pérdida de generalidad, suponga un_i <b_i, 1<= i <=k.

Ahora, para poder mostrar que N no es mejor, es suficiente para demostrar que ninguno de un_i se puede factorizar más. Y también sabemos que un_i <= sqrt(N) y así necesitas verificar hasta sqrt(N) que cubrirá todo un_i. Y, por lo tanto, podrás concluir si N es primo.

...

Answer 8

Entonces, para verificar si un número N es primo o no. Solo necesitamos verificar si N es divisible por los números <= Sqroot (n). Esto se debe a que, si factorizamos N en 2 factores, dicen x e y, es decir. N = xY. Cada uno de X e Y no puede ser menor que Sqroot (N) porque entonces, XY <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).

Answer 9

Digamos que tenemos un número "A", que no es primo [no es primo/número compuesto, un número que puede dividirse de manera uniforme por números distintos a 1 o en sí mismo. Por ejemplo, 6 se puede dividir 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, 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" 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.

Answer 10

Deje que n no sea Prime. Por lo tanto, tiene al menos dos factores enteros mayores que 1. Sea F los factores más pequeños de N. Supongamos 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.

Answer 11

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, luego volvemos n:

p*p = n

Se puede reescribir como:

a*b = n

Dónde p = a = b. Si a aumenta, entonces b disminuye para mantener a*b = n. Por lo tanto, p es el límite superior.

Answer 12

Para probar la primalidad de un número, norte, uno esperaría un bucle como seguir 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 dado 1 <i <n, verifica si N/I es un entero (deja el resto 0). Si existe una I para la cual N/I es un entero, entonces podemos estar seguros de que N no es un número primo, momento en el que termina el bucle. Si no i, n/i es un entero, entonces n es primo.

Como con cada algoritmo, preguntamos: ¿Podemos hacerlo mejor?

Veamos lo que está sucediendo en el bucle anterior.

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

Y la secuencia de verificaciones enteras 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 alcanza 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 so n> a> 1.

Entonces, A y K son enteros entre 1 y N (exclusivos). Dado que llego a todos los enteros 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, necesitamos 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).

Answer 13

Cualquier número compuesto es un producto de primos.

Digamos n = p1 * p2, dónde p2 > p1 Y son primos.

Si n % p1 === 0 después norte es un número compuesto.

Si n % p2 === 0 Entonces adivina que n % p1 === 0 ¡también!

Entonces no hay forma de que si n % p2 === 0 pero n % p1 !== 0 al mismo tiempo. En otras palabras, si un número compuesto norte puede dividirse uniformemente porP2, P3 ... PI (su factor mayor) debe dividirse por su factor más bajo P1 también. Resulta que el factor más bajo p1 <= Math.square(n) siempre es cierto.