Una forma rápida, dice en un minuto, para deducir si $1037$ es un número primo

Question

Así que con $1037 = 17 \cdot 61$, existe un método rápido para deducir que no es un número primo?

Decir $1037 = 10^3+6^2+1$. Qué $a^3 + b^2 + 1$ factorizar de alguna manera?

Como parte de sus entrevistas, una empresa está preguntando si un número es primo. Nunca he estudiado la teoría de los números, y yo no soy consciente de que una estrategia para que esto, aparte de polinomio factorización.

Supongo que para un número que te dan, tendría que no ser la mejor, como la única manera de ver que un número es un primer mano es probar todos los números primos por debajo de $\sqrt{N}$.

Answer 1

$u\mid v$ se lee como "$u$ divide $v$" e $u\nmid v$ se lee como "$u$ no divide $v$."

---

Obviamente $2\nmid 1037$, ya que tiene una extraña último dígito.

Por la "Divisibilidad por $3$ Regla," se sigue que $3\nmid 1037$ desde $3\nmid 1+0+3+7=11$.

Obviamente $5\nmid 1037$ desde el último dígito no es $0$ ni $5$.

Si $7\mid 1037$ $7\mid 1037-7=1030$ pero $1030=103\times 10$, e $103$ es el primer y $7\nmid 10$.

Si $11\mid 1037$ $11\mid 1037-77=960$ pero $960=96\times 10$ $11\mid 99$ $11\nmid 96$ ya que es un resto de $3$ (y obviamente $11\nmid 10$).

Trate de $13$ este tiempo, y, a continuación, para $17$. Verás que funciona para $17$, lo que indica que el $17\mid 1037$ $1037$ no es primo.

---

Usted puede probar este método para todos los números, y sólo es necesario probar los primeros números primos menos de la raíz cuadrada del número de pruebas; por ejemplo, dice que no sabe si $61$ es un número primo. A continuación, aplicar este método.

Ahora, $64=8^2$ $\sqrt{61}$ está muy cerca de la $8$. Y desde $7^2=49<61$, entonces todo lo que necesita hacer es ver si $2,3,5$ o $7$ brecha $61$. Si no, entonces $61$ es el primer (y lo es).

Este método no tiene un nombre oficial, por lo que bien podría ser llamado un "juicio de divisibilidad de verificación" primos. Gracias a los usuarios que se comenta más abajo que me corrigió como yo pensaba que este método era el siguiente.

Un conocido método es la "Criba de Eratóstenes."

---

Sugerencia:

Un buen número de números primos para recordar la parte superior de vuestra cabeza están todos los números primos hasta el $127$. Esto me ha ayudado, y $127$ es un bonito número especial. Hay muchas buenas propiedades acerca de $127$; por ejemplo, $127$ es una de Mersenne prime (un primo de la forma $2^p-1$ primer $p$), y es el $31$st primer número, $31$ siendo también de Mersenne prime.

Si usted quiere recordar más números primos después de $127$, se puede. (Yo hice todo el camino hasta el $383$, por lo que es posible.)

---

Disculpas si esta respuesta es principalmente de opinión.

Answer 2

Hay varios métodos para decidir primalidad, algunos probabilístico (el resultado no es seguro, pero la más ejecutar el algoritmo de la forma más segura de saber la respuesta) y hay métodos determinísticos (deciden por cierto). Aunque todas estas trabajando de manera eficiente en los números que son mayores que $1037$.

Con los números de este tamaño la comprobación de todos los números parece ser la forma más eficiente. Hay, por supuesto, hay algunos casos especiales, pero si usted consigue un número de este tamaño que usted debe hacer para comprobar si es que es (fácil), divisible por $3$ (el digitsum es divisible por $3$) $5$ (termina con $0$ o $5$) y así sucesivamente. Si usted tiene una calculadora a la mano, no tarda más de un minuto desde $\sqrt{1037}\approx 32$, por lo que usted sólo tiene que comprobar los números primos hasta el $31$.

Seguramente no significa que este tipo de pruebas, pero me gustaría añadir algunos enlaces para que veais la diferencia

Probablilistic prueba de ello es la llamada de Miller-Rabin prueba.

Y para determinista Pollards $p-1$ y Lenstras de curva elíptica factorización es una forma rápida y eficiente.

Incluso la diferencia de cuadrados puede funcionar bien:

$N$ es de tener en cuenta, encontrar una $b^2$ tal que $N+b^2$ es un cuadrado, decir $a^2$ y, a continuación,

$$ N+b^2=a^2 $$ así $$ N=a^2-b^2=(a-b)(a+b) $$

Answer 3

Sospecho que el entrevistador está más interesado en su enfoque para responder a la pregunta que en la velocidad de tu cálculo mental. Como un enfoque práctico, me descartar 2,3 y 5 como factores inmediatamente y luego utilizar la calculadora en mi teléfono para comprobar la divisibilidad por otros primos pequeños. Para 1037 basta verificar números primos hasta 31. Pero lo más importante es hablar a través de lo que está haciendo y por qué lo está haciendo.

Answer 4

Como otros han señalado, sólo se necesita comprobar los números primos hasta el 31. Por supuesto que voy a tomar un tiempo si tienes que hacerlo por la división larga - he aquí un par de accesos directos.

2: El último dígito no es uniforme, por lo que obviamente 1037 no es divisible por 2.

3: La suma de los dígitos es 11, que no es divisible por 3, por lo que 1037 no es divisible por 3.

5: El último dígito no 5 o 0, por lo que 1037 no es divisible por 5.

7: Si 1037 fueron divisible por 7, por lo que sería 1030. Si 1030 fueron divisible por 7, 103 sería demasiado. Si 103 fueron divisible por 7, por lo que sería de 110, que es $2 \cdot 5 \cdot 11$ y por lo tanto no divisible por 7. Así 1037 no es divisible por 7.

11: $1 - 0 + 3 - 7 = -3$, que no es divisible por 11, así que 1037 no es divisible por 11.

13: Si 1037 fueron divisible por 13, a continuación, $1050 = 1037 + 13$ también sería. Si $1050$ fueron divisible por 13, $105$ sería demasiado. Pero $105 = 3 \cdot 5 \cdot 7$, por lo que no es divisible por 13, por lo que tampoco es 1037.

17: 1037 es divisible por 17 sólo si $1037 - 17 = 1020$ es. 1020 es divisible por 17 sólo si $102$ es. $102 = 2 \cdot 51 = 2 \cdot 3 \cdot 17$, por lo que es divisible por 17, por lo que 1037 es divisible por 17, por lo que 1037 no es primo.

Nota: Estos enfoques no hacer un buen trabajo de factoring - es un poco difícil para relajarse que el último argumento de averiguar lo $1037/17$ es. Pero si la pregunta es "¿es el primer", esto debería funcionar bien.

Answer 5

Usted no es probable que obtener incluso un moderado gran número aleatorio para el factor. Además de las pruebas en las otras respuestas, podría ayudar (y es bueno saber) la prueba de $11$ - calcular la alternancia de suma de los dígitos y buscar $0$.

En el siguiente nivel, el hecho de que $1001 = 7 \times 11 \times 13$ significa que usted puede probar la divisibilidad para todos aquellos que mediante el cálculo de la alternancia suma de tres dígitos bloques, a continuación, sólo las pruebas de los tres dígitos del resultado.

Finalmente, $91$ es el único número a menos de $100$ que "se parece a un primer" pero no lo es. Eso es porque la iguala, múltiplos de $3$ y $5$, $77$ y $49$ son claramente compuesto. Los otros son los números que se ven como los números primos.