Para encontrar si N es un número primo, solo tenemos que buscar todos los números menores o iguales a sqrt (N). ¿Porqué es eso? Estoy escribiendo un código C para tratar de entender una razón detrás de él.Encuentra un número primo?
N es primo si es un número entero positivo que es divisible por exactamente dos números enteros positivos, 1 y N. Dado que los divisores de un número no puede ser mayor que el número, esto da lugar a una sencilla prueba de primalidad:
[2, N-1], entonces N es primo. De lo contrario, N no es primo.Sin embargo, sería bueno modificar esta prueba para hacerlo más rápido. Entonces, investiguemos.
Tenga en cuenta que los divisores de N aparecen en pares. Si N es divisible por un número M, entonces también es divisible por N/M. Por ejemplo, 12 es divisible por 6, y también por 2. Además, si es M >= sqrt(N), entonces N/M <= sqrt(N).
Esto significa que si ningún número inferior o igual a sqrt (N) divide N, ningún número mayor que sqrt (N) divide N tampoco (excepto 1 y N ellos mismos), de lo contrario surgiría una contradicción.
Así que tenemos una mejor prueba:
[2, sqrt(N)], entonces N es primo. De lo contrario, N no es primo.si considera el razonamiento anterior, debería ver que un número que pasa esta prueba también pasa la primera prueba, y un número que falla esta prueba también falla la primera prueba. Las pruebas son por lo tanto equivalentes.
por favor muestra que no tenemos ni idea ... – vehomzzz
Un número compuesto (uno que no es primo, o 1) tiene al menos 1 par de factores, y se garantiza que uno de los números de cada par es menor o igual que la raíz cuadrada del número (que es sobre lo que preguntas).
Si hace coincidir la raíz cuadrada del número, obtiene el número en sí (sqrt(n) * sqrt(n) = n), por lo que si hizo uno de los números más grandes (que sqrt(n)) tendría que hacer el otro más pequeño. Si solo revisa los números 2 a sqrt(n), habrá verificado todos los factores posibles, ya que cada uno de esos factores se vinculará con un número que es mayor que sqrt(n) (excepto, por supuesto, si el número es de hecho un cuadrado de algún otro número, como 4, 9, 16, etc. ... pero eso no importa ya que usted sabe que no son primos, sino que son fácilmente factorizados por el propio sqrt(n)).
Porque en el peor de los casos, el número n se puede expresar como .
Si el número se puede expresar de manera diferente, que los hombres que uno de los divisores será menor que a = sqrt(n), pero el otro puede ser mayor.
La razón es simple, cualquier número mayor que el sqrt hará que el otro multiplicador sea más pequeño que el sqrt. En tal caso, ya deberías haberlo comprobado.
Vamos n = un × b ser compuesto.
Supongamos un> sqrt (n) y b> sqrt (n).
un × b> sqrt (n) x sqrt (n)
un × b>n
Pero sabemos un × b = n, por lo tanto un < sqrt (n) o b < sqrt (n).
Dado que sólo necesita saber un o b para mostrar n es compuesto, sólo tiene que comprobar los números hasta sqrt (n ) para buscar un número tal.
No relacionado con la programación – ChssPly76
@ ChssPly76: Creo que esta es una consulta de algoritmos completamente válida. – Artelius
Hmm ... Estoy escribiendo código para implementar esto. ¿Cómo no está programando de nuevo? – vehomzzz