Números primos

Question

Tengo un programa que determina si un número es primo o no. El algoritmo básico simplemente comprueba el número es divisible por 1 y sí mismo.

Mi pregunta es, hay un límite superior para la comprobación de los números de la divisibilidad sin un resto? Si sí, ¿puedes explicar por qué?

Mi "tripa" la sensación es que cualquier número por encima de 1/2", el número se comprueba debe ser ignorado, pero no puedo demostrarlo.

Answer 1

Voy a tratar de explicar mediante un ejemplo.

Vamos a ver si $37$ es un número primo.

• Obviamente no es divisible por $2$,
• no es divisible por $3$ (debido a $3+7=10$ que no es divisible por $3$),
• y no es divisible por cinco (debido a que el último dígito es el no $0$ o $5$).

Estos son todos los posibles candidatos para los factores de $37$, y voy a tratar de explicar por qué. Si $7$ es un factor de $37$ (lo que significaría que $37$ es divisible por $7$, y por lo tanto no es un primo), a continuación, el otro factor que debe ser mayor o igual a $7$, puesto que ya se ha demostrado que no hay ningún factor de menos de $7$. Pero $7 \cdot 7 = 49 > 37$. Entonces no hay ninguna razón para tratar con mayor factores, debido a que el producto tendría que ser aún mayor.

Así hemos demostrado que para $37$, solo tenemos que tratar de dividir por $2$, $3$ y $5$. Como ambos Raeder y Theo ha señalado que no tenemos que ir más allá de la raíz cuadrada del número que desea comprobar y espero que mi ejemplo ayuda a explicar por qué.

Edit: Como Picakhu sugerido, voy a explicar por qué estos métodos para comprobar la divisibilidad por $2$, $3$, y $5$ obras.

Comprobar la divisibilidad por $2$ $5$
Al comprobar la divisibilidad por $2$ o $5$, es suficiente para comprobar que sólo el último dígito es divisible $2$ o $5$ respectivamente. Esto tiene que ver con el hecho de que estamos utilizando $10$, que es el producto de $2$$5$, como nuestra base. Voy a explicar el uso de números de tres dígitos. La explicación sería muy similar si se hubiera utilizado más dígitos. Todos los números de $abc$ (donde $a$ es el primer dígito, $b$ el segundo, y $c$ el tercero) puede escribirse en la forma $$abc = a\cdot 10^2 + b\cdot 10^1 + c\cdot 10^0 = a \cdot 100 + b \cdot 10 + c.$$ La notación estoy usando puede ser confuso. Para aclarar: Si, por ejemplo, $a=b=c=4$,$abc = 444 \neq 4\cdot 4\cdot 4$. Vamos a ver qué pasa si dividimos por 2. $$\frac{abc}{2} = \frac{a \cdot 100}{2} + \frac{b \cdot 10}{2} + \frac{c}{2} = a \cdot 50 + b \cdot 5 + \frac{c}{2}$$ Nos damos cuenta de que este es un número entero si y sólo si $\frac{c}{2}$ es un número entero, no importa lo $abc$ es. Obtenemos un resultado similar si dividimos por $5$. $$\frac{abc}{5} = a \cdot 20 + b \cdot 2 + \frac{c}{5}$$ Por lo tanto es suficiente para comprobar el último dígito.

Comprobar la divisibilidad por $3$
Al comprobar la divisibilidad por $3$, es suficiente para comprobar que la suma de los dígitos es divisible por $3$. Esto es más fácil para mostrar el uso de aritmética modular. Tenga en cuenta que $10 \equiv 1 \pmod 3$. Si usamos nuestro número de tres dígitos $abc$ nuevo vemos que $$a \cdot 10^2 + b \cdot 10 + c \equiv a \cdot 1 + b \cdot 1 + c = a + b + c \pmod 3.$$ Por lo tanto $abc$ es divisible por $3$ si y sólo si $a + b + c$ es divisible por $3$.

Wikipedia tiene una lista de más pruebas de divisibilidad como estos.

Answer 2

En primer lugar, supongo que ha divisible solamente por 1 y sí mismo.

De la pregunta, usted sólo necesita comprobar los factores de seguridad de la raíz cuadrada del número, ya que por entonces usted tendrá que encontrar todos los productos posibles menor que el número dado.

Por el camino, su corazonada es correcta, ya que dos veces por algo más de la mitad de su número será mayor que el número.

Si algo está claro, que me gustaría aclarar.

EDIT: veo que Theo ha explicado por qué esto es cierto en una idea mucho más clara de la moda en los comentarios.