Para encontrar si $a$ es un número primo

Question

He estado usando esta regla para determinar si un número es un número primo, pero no se como demostrarlo. ¿Por qué tiene que ser $\sqrt{a}$?

Si no es divisible por todos los números primeros menos que o igual a $a$ $\sqrt{a}$, $a$ es un número primo.

Answer 1

Asumir $a$ no es un número primo. Entonces se puede escribir como $a = bc$ $b, c \ge 2$. Entonces el más pequeño de $b, c$ es menor o igual a $\sqrt a$, de lo contrario el producto sería mayor que $\sqrt a \, \sqrt a = a$. Este pequeño es entonces un primer sí mismo o tiene un factor primordial que es incluso más pequeño.

Answer 2

Divisores vienen en pares. Si divide a $n$ $a$, no así $a/n$, $\sqrt{a}\sqrt{a}=a$, uno de los factores en un par debe ser menor o igual a $\sqrt{a}$.

Answer 3

Sólo otro punto de vista

Supongamos que $a$ es divisible por un primo $p$. Esto significa que: $$a = p \cdot k \Rightarrow p = \frac{a}{k}.$$ Por otra parte, supongamos que el $p > \sqrt{a}$, entonces:

$$\frac{a}{k} > \sqrt{a} \Rightarrow k < \sqrt{a}.$$

Esto significa que sólo puedo usar los números primos $p \in [\sqrt{a}, a]$ a determinar si $a$ es el primer lugar de la serie a $[0, \sqrt{a}]$.

Que es el conjunto que mejor se adapte para el algoritmo?

Supongo que los más pequeños, ya que tienen un menor número de números primos para ser probado. El conjunto $[\sqrt{a}, a]$ tiene una longitud de $a-\sqrt{a}$, mientras que el conjunto $[0, \sqrt{a}]$ tiene una longitud de $\sqrt{a}$.

Observe que: $$\sqrt{a} < a-\sqrt{a} \Rightarrow 2\sqrt{a} < a \Rightarrow \sqrt{a} > 2 \Rightarrow a > 4.$$

En general, usted quiere probar un número $a$ más grande que la de $4$. Por esta razón, sólo se observa para el conjunto de $[0, \sqrt{a}]$... es simplemente más rápido!

---

Ejemplo.

Tome $a = 77$ y el aviso de que $\sqrt{a} \simeq 8.78$. Si utiliza el conjunto de $[0, \sqrt{a}]$, usted tendrá que comprobar si $a$ es divisible por $3,5,7$ (sólo tres números). Por otro lado, si usted elige el conjunto $[\sqrt{a}, a]$, usted tendrá que comprobar si $a$ es divisible por $11, 13, 17, 19, 23, 29, 31, 37, ...$. Hey, esto es demasiado, no?!

Answer 4

Que $ab=p$ donde $a,b$ son posibles factores de candidato ideal $p$.

Si encuentras un factor $b \geq \sqrt{p}$, entonces el $a \leq \sqrt{p}$.

Pero si comprueban todas las $a \leq \sqrt{p}$ y no encuentran los factores...

Answer 5

Para cada divisor principal de $n$ que es inferior a $n$ y mayor de $\sqrt{n}$, debe haber un número primo inferior a $\sqrt{n}$ que divide $n$.

Esto sigue del hecho de que es imposible para un número $n$ tienen dos divisores primeros $p$ y $q$ que fueron desde entonces más de $\sqrt{n}$, entonces su producto es %#% $ #%

Por lo tanto necesitamos comprobamos sólo los números primos en el rango $$pq>(\sqrt{n})^2=n$ a ver si reparten $1,...,\sqrt{n}$.