Por que verificamos a raiz quadrada de um número primo para determinar se é primo?

Para testar se um número é primo ou não, por que precisamos testar se ele é divisível somente até a raiz quadrada desse número?

Se um número n não é primo, ele pode ser fatorado em dois fatores b :

 n = a*b 

Se tanto a como b fossem maiores que a raiz quadrada de n , a*b seria maior que n . Portanto, pelo menos um desses fatores deve ser menor ou igual à raiz quadrada de n , e para verificar se n é primo, precisamos apenas testar os fatores menores ou iguais à raiz quadrada.

Vamos dizer que m = sqrt(n) então m × m = n . Agora, se n não é um primo, então n pode ser escrito como n = a × b , então m × m = a × b . Observe que m é um número real, enquanto n , b são números naturais.

Agora pode haver 3 casos:

  1. a> m ⇒ b
  2. a = m ⇒ b = m
  3. a m

Em todos os 3 casos, min(a, b) ≤ m . Portanto, se procurarmos até m , estaremos obrigados a encontrar pelo menos um fator de n , o que é suficiente para mostrar que n não é primo.

Porque se um fator é maior que a raiz quadrada de n, o outro fator que iria multiplicar com ele para igual n é necessariamente menor que a raiz quadrada de n.

Uma explicação mais intuitiva seria:

A raiz quadrada de 100 é 10. Digamos axb = 100, para vários pares de a e b.

Se a = = b, então eles são iguais e são a raiz quadrada de 100, exatamente. Qual é 10.

Se um deles é menor que 10, o outro tem que ser maior. Por exemplo, 5 x 20 == 100. Um é maior que 10, o outro é menor que 10.

Pensando em axb, se um deles desce, o outro deve ficar maior para compensar, então o produto fica em 100. Eles giram em torno da raiz quadrada.

A raiz quadrada de 101 é de cerca de 10.049875621. Então, se você está testando o número 101 para primality, você só precisa testar os números inteiros até 10, incluindo 10. Mas 8, 9 e 10 não são eles próprios primos, então você só tem que testar através de 7, que é primo.

Porque se há um par de fatores com um dos números maiores que 10, o outro do par deve ser menor que 10. Se o menor não existir, não há fator maior correspondente de 101.

Se você está testando 121, a raiz quadrada é 11. Você tem que testar os números inteiros de 1 a 11 (inclusive) para ver se ele vai uniformemente. 11 vai 11 vezes, então 121 não é primo. Se você tivesse parado às 10 e não tivesse testado 11, teria perdido 11.

Você tem que testar todo número inteiro maior que 2, mas menor ou igual à raiz quadrada, assumindo que você está apenas testando números ímpares.

`

Suponha que n não seja um número primo (maior que 1). Então, existem números b tais que

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

Multiplicando a relação a< =b por b obtemos:

 a^2 < = ab ab <= b^2 

Portanto: (note que n=ab )

 a^2 < = n <= b^2 

Daqui: (note que b são positivos)

 a < = sqrt(n) <= b 

Portanto, se um número (maior que 1) não for primo e testarmos a divisibilidade até a raiz quadrada do número, encontraremos um dos fatores.

Vamos supor que o inteiro dado N não seja primo,

Então N pode ser fatorado em dois fatores b , 2 < = a, b < N tal que N = a*b . Obviamente, ambos não podem ser maiores que sqrt(N) simultaneamente.

Vamos supor sem perda de generalidade que a é menor.

Agora, se você não encontrou nenhum divisor de N pertencente ao intervalo [2, sqrt(N)] , o que isso significa?

Isso significa que N não possui nenhum divisor em [2, a] como a < = sqrt(N) .

Portanto, a = 1 e b = n e, portanto, por definição, N é primo .

...

Leitura adicional se você não estiver satisfeito:

Muitas combinações diferentes de (a, b) podem ser possíveis. Vamos dizer que eles são:

(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 ), ....., (a k , b k ). Sem perda de generalidade, assuma a i i , 1< = i <=k .

Agora, para ser capaz de mostrar que N não é primo, é suficiente mostrar que nenhum de um pode ser fatorado ainda mais. E também sabemos que a i < = sqrt(N) e, portanto, você precisa verificar até sqrt(N) que cobrirá todos os i . E, portanto, você será capaz de concluir se N é primo ou não.

...

É tudo realmente apenas usos básicos de Factorization e Square Roots.

Pode parecer abstrato, mas na realidade reside simplesmente no fato de que o fatorial máximo possível de um número não primo teria que ser sua raiz quadrada porque:

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

Dado que, se qualquer número inteiro acima de 1 e abaixo ou acima de sqrroot(n) dividir uniformemente em n , então n não poderá ser um número primo.

Exemplo de pseudocódigo:

 i = 2; is_prime = true; while loop (i < = sqrroot(n)) { if (n % i == 0) { is_prime = false; exit while; } ++i; } 

Então, para verificar se um número N é Prime ou não. Precisamos apenas verificar se N é divisível por números < = SQROOT (N). Isto porque, se nós fatorarmos N em quaisquer 2 fatores, digamos X e Y, ie. N = X Y. Cada um dos X e Y não pode ser menor que SQROOT (N) porque, então, X Y N

Portanto, um fator deve ser menor ou igual a SQROOT (N) (enquanto o outro fator é maior ou igual a SQROOT (N)). Então, para verificar se N é Prime, precisamos apenas verificar esses números < = SQROOT (N).

Seja n não primo. Portanto, ele tem pelo menos dois fatores inteiros maiores que 1. Seja f o menor de n tais fatores. Suponha que f> sqrt n. Então n / f é um inteiro LTE sqrt n, portanto menor que f. Portanto, f não pode ser o menor fator de n. Reductio ad absurdum; O menor fator de n deve ser LTE sqrt n.

Digamos que temos um número “a”, que não é primo [não-primo / número composto significa – um número que pode ser dividido igualmente por números diferentes de 1 ou de si mesmo. Por exemplo, 6 pode ser dividido igualmente por 2 ou por 3, assim como por 1 ou 6].

6 = 1 × 6 ou 6 = 2 × 3

Então, agora, se “a” não é primo, então ele pode ser dividido por dois outros números e vamos dizer que esses números são “b” e “c”. Que significa

a = b * c.

Agora, se “b” ou “c”, qualquer um deles é maior que a raiz quadrada de “a” que a multiplicação de “b” e “c” será maior que “a”.

Então, “b” & “c” é sempre < = raiz quadrada de "a" para provar a equação "a = b * c".

Por causa do motivo acima, quando testamos se um número é primo ou não, só verificamos até a raiz quadrada desse número.

Para testar a primalidade de um número, n , seria de se esperar que um loop como o seguinte, em primeiro lugar:

 bool isPrime = true; for(int i = 2; i < n; i++){ if(n%i == 0){ isPrime = false; break; } } 

O que o loop acima faz é o seguinte: para um determinado 1 , ele verifica se n / i é um inteiro (deixa o resto 0). Se existe um i para o qual n / i é um inteiro, então podemos ter certeza de que n não é um número primo, ponto no qual o loop termina. Se para nenhum i, n / i é um inteiro, então n é primo.

Como em todos os algoritmos, perguntamos: podemos fazer melhor?

Vamos ver o que está acontecendo no loop acima.

A seqüência de eu vou: i = 2, 3, 4, ..., n-1

E a seqüência de verificações inteiras vai: j = n / i, que é n / 2, n / 3, n / 4, ..., n / (n-1)

Se para algum i = a, n / a é um inteiro, então n / a = k (inteiro)

ou n = ak, claramente n> k> 1 (se k = 1, entao a = n, mas nunca alcanço n; e se k = n, entao a = 1, mas eu inicio a forma 2)

Além disso, n / k = a, e como dito acima, a é um valor de i so n> a> 1.

Assim, a e k são ambos inteiros entre 1 e n (exclusivo). Desde então, eu alcanço todos os inteiros nessa faixa, em alguma iteração i = a, e em alguma outra iteração i = k. Se o teste de primalidade de n falhar por min (a, k), ele também falhará no máximo (a, k). Então, precisamos checar apenas um desses dois casos, a menos que min (a, k) = max (a, k) (onde dois cheques se reduzem a um) ie, a = k, ponto em que a * a = n, que implica um = sqrt (n).

Em outras palavras, se o teste de primalidade de n falhasse em algum i> = sqrt (n) (isto é, max (a, k)), então também falharia para algum i < = n (isto é, min (a , k)). Então, seria suficiente se nós rodássemos o teste de i = 2 para sqrt (n).