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

392

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

Pan
fonte
33
porque se n = a*be a <= bentão a*a <= a*b = n.
Will Ness
7
Para esclarecer, isso significa que temos que testar apenas até floor(sqrt(n)).
Acumenos

Respostas:

659

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

n = a * b

Agora ae bnão pode ser maior que a raiz quadrada de n, desde então o produto a * bseria maior que sqrt(n) * sqrt(n) = n. Portanto, em qualquer fatoração de n, pelo menos um dos fatores deve ser menor que a raiz quadrada de ne, se não conseguirmos encontrar fatores menores ou iguais à raiz quadrada, ndeve ser primo.

Sven Marnach
fonte
Como sqrt(n)precisa ser preciso o suficiente para que essa propriedade seja mantida, pois estamos usando pontos flutuantes.
Benoît
@ Benoît Você sempre pode usar a verificação em i * i <= nvez de i <= sqrt(n)evitar a complexidade dos números de ponto flutuante.
Sven Marnach
348

Digamos m = sqrt(n)então m × m = n. Agora, se nnão é primo, npode ser escrito como n = a × b, então m × m = a × b. Tenha em conta que mé um número real enquanto n, ae bsão números naturais.

Agora pode haver três casos:

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

Nos 3 casos min(a, b) ≤ m,. Portanto, se procurarmos atém , encontraremos pelo menos um fator de n, o suficiente para mostrar que nnão é primo.

BiGYaN
fonte
4
n = 12 m = sqrt (12) = 3,46, a = 2, b = 6. n = m m, isto é, 12 = 3,46 * 3,46 e n = a b, = 12 = 2 * 6. Agora, condicione 3. a <m <b, isto é, 2 <3,46 <6. Portanto, para verificar o primo, precisamos apenas verificar o número menor que 3,46, que é 2, para descobrir que o número não é primo. Portanto, verifique a divisibilidade por números menores ou iguais a (se n = 4, m = a = b = 2) raiz quadrada de n.
Anukalp
2
Acho que devemos destacar a suposição primeiro. Suponha n is not a prime, e prove, caso contrário, é primo.
Huei Tan
Na verdade, não estou convencido de que seja uma resposta melhor. É uma resposta correta, mas realmente não responde à pergunta. Apenas descreve algumas outras dinâmicas em torno dos números primos e do sqrt. As respostas de @ Sven são sucintas e não criam mais perguntas no processo.
Jon M
11
Voltei para a última versão boa. você perdeu quando alguém removeu desnecessariamente uma palavra ('daí'), necessária para o fluxo.
quer
55

Como se um fator é maior que a raiz quadrada de n, o outro fator que se multiplicaria para igual a n é necessariamente menor que a raiz quadrada de n.

patros
fonte
37

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 for menor que 10, o outro deverá ser maior. Por exemplo, 5 x 20 == 100. Um é maior que 10, o outro é menor que 10.

Pensando em axb, se um deles cair, o outro deve aumentar para compensar, para que o produto fique em 100. Eles giram em torno da raiz quadrada.

A raiz quadrada de 101 é de cerca de 10.049875621. Portanto, se você estiver testando o número 101 quanto à primalidade, precisará experimentar os números inteiros até 10, incluindo 10. Mas 8, 9 e 10 não são eles mesmos primos, então você só precisa testar até 7, o que é prime.

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

Se você estiver testando 121, a raiz quadrada é 11. Você precisa testar os números inteiros primos 1 a 11 (inclusive) para ver se eles são iguais. 11 passa 11 vezes, portanto 121 não é primo. Se você tivesse parado aos 10 e não testado 11, teria perdido 11.

Você deve testar todos os números inteiros primos maiores que 2, mas menores ou iguais à raiz quadrada, assumindo que você esteja testando apenas números ímpares.

`

Archit Garg
fonte
3
"Pensando no axb, se um deles cair, o outro deve aumentar para compensar, para que o produto fique em 100. Eles giram em torno da raiz quadrada." Meu momento aha! Obrigado!
Brian Wigginton
Esta é a melhor resposta.
JeanieJ 17/03
19

Suponha que nnão seja um número primo (maior que 1). Portanto, existem números ae btais que

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

Ao multiplicar a relação a<=bpor ae bobtemos:

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

Portanto: (observe que n=ab)

a^2 <= n <= b^2

Portanto: (Observe que ae bsão positivos)

a <= sqrt(n) <= b

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

LoMaPh
fonte
8

Vamos supor que o número inteiro fornecido N não seja primo,

Então N pode ser fatorado em dois fatores ae b, 2 <= a, b < Ntal que N = a*b. Claramente, os dois não podem ser maiores quesqrt(N) simultaneamente.

Vamos assumir, sem perda de generalidade, que a é menor.

Agora, se você não encontrar nenhum divisor de Npertença no intervalo[2, sqrt(N)] , o que isso significa?

Isto significa que Nnão têm qualquer divisor em [2, a]comoa <= sqrt(N) .

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

...

Leitura adicional se você não estiver satisfeito:

Muitas combinações diferentes de (a, b) podem ser possíveis. Digamos 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 <b i ,1<= i <=k .

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

...


fonte
7

É tudo realmente apenas usos básicos de fatoração e raízes quadradas.

Pode parecer abstrato, mas, na realidade, simplesmente reside 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 1e abaixo ou até for sqrroot(n)dividido uniformemente em n,n não pode ser um número primo.

Exemplo de pseudo-código:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}
Super Cat
fonte
Observação brilhante. Usando esta observação para criar uma guarddeclaração no Swift em conjunto com este prático stackoverflow.com/a/25555762/4475605 para fazer uma saída antecipada de um cálculo, em vez de desperdiçar energia computacional. Obrigado por postar.
Adrian
@ Adrian Devo confessar que, depois de voltar a esta resposta, encontrei um erro no momento da postagem. Você não pode executar a divisão em um 0 e, em teoria, se você pudesse ++ise tornar o número 1, que sempre retornaria falso (porque 1 se divide em tudo). Corrigi a resposta acima.
Super Cat
Sim ... eu resolvi isso no meu código ... sua observação de raiz quadrada é uma ótima maneira de lançar fora um valor não primo antes de começar a executar os cálculos. Eu estava sendo morto por um grande número que acabou sendo uma grande perda de tempo. Também aprendi que esse algoritmo também pode reduzir substancialmente o tempo de processamento em grandes números. en.wikipedia.org/wiki/Miller –Rabin_primality_test
Adrian
6

Portanto, para verificar se um número N é Prime ou não. Precisamos apenas verificar se N é divisível por números <= SQROOT (N). Isso ocorre porque, se fatorarmos N em quaisquer 2 fatores, diga X e Y, ou seja. N = X Y. Cada um de X e Y não pode ser menor que SQROOT (N) porque, então, X Y <N Cada um de X e Y não pode ser maior 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 que ou igual a SQROOT (N)). Portanto, para verificar se N é Prime, precisamos apenas verificar esses números <= SQROOT (N).

rhea rodrigues
fonte
3

Digamos que tenhamos um número "a", que não é primo [não significa número primo / composto - um número que pode ser dividido igualmente por números diferentes de 1 ou ele próprio. Por exemplo, 6 podem ser divididos igualmente por 2 ou 3, bem como por 1 ou 6].

6 = 1 × 6 ou 6 = 2 × 3

Então agora se "a" não é primo, ele pode ser dividido por outros dois números e digamos que esses números sejam "b" e "c". Que significa

a = b * c.

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

Portanto, "b" ou "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, verificamos apenas a raiz quadrada desse número.

Abu Naser Md Shoaib
fonte
11
b & c <= Math.sqrt (n) ?; Deve ser bastante b || c (b ou c) desde que se n = 6, b = 3, c = 2 então Math.sqrt (n)> c.
daGo
Obrigado amigo pela correção. fazendo a correção. :)
Abu Naser Md Shoaib
2

Dado qualquer número n, uma maneira de encontrar seus fatores é obter a raiz quadrada p:

sqrt(n) = p

Obviamente, se multiplicarmos ppor si só, voltaremos n:

p*p = n

Pode ser reescrito como:

a*b = n

Onde p = a = b. Se aaumenta, bdiminui para manter a*b = n. Portanto, pé o limite superior.

Atualização: Estou relendo esta resposta novamente hoje e ficou mais clara para mim. O valor pnão significa necessariamente um número inteiro porque, se for, nnão seria um primo. Portanto, ppoderia ser um número real (ou seja, com frações). E, em vez de passar por toda a gama de n, agora só precisamos passar por toda a gama de p. O outro pé uma cópia espelhada, de modo que reduzimos o intervalo pela metade. E então, agora estou vendo que podemos realmente continuar refazendo square roote fazendo isso ppara mais da metade do intervalo.

truthadjustr
fonte
1

Seja n não primo. Portanto, ele possui pelo menos dois fatores inteiros maiores que 1. Seja f o menor dos fatores de n. Suponha 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.

Reb.Cabin
fonte
1

Qualquer número composto é um produto de números primos.

Digamos n = p1 * p2, onde p2 > p1e eles são primos.

Se n % p1 === 0então n é um número composto.

Se n % p2 === 0então adivinhe n % p1 === 0também!

Portanto, não há como se, n % p2 === 0mas n % p1 !== 0ao mesmo tempo. Em outras palavras, se um número composto n pode ser dividido igualmente por p2, p3 ... pi (seu fator maior), ele também deve ser dividido pelo fator mais baixo p1 . Acontece que o fator mais baixo p1 <= Math.square(n)é sempre verdadeiro.

daGo
fonte
Se você está curioso para saber por que é verdade, o @LoMaPh explicou bastante o fato em sua resposta. Eu adicionei a minha resposta porque tive realmente dificuldades para visualizar e entender outras respostas fornecidas. Apenas não clicou.
DaGo
0

Para testar a primalidade de um número, n , seria de esperar 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 dado 1 <i <n , ele verifica se n / i é um número inteiro (deixa o restante 0). Se existe um i para o qual n / i é um número inteiro, podemos ter certeza de que n não é um número primo, momento em que o loop termina. Se para no i, n / i é um número inteiro, então n é primo.

Como em todo algoritmo, perguntamos: podemos fazer melhor?

Vamos ver o que está acontecendo no loop acima.

A sequência de i é: i = 2, 3, 4, ..., n-1

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

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

ou n = ak, claramente n> k> 1 (se k = 1, então a = n, mas eu nunca alcança n; e se k = n, então a = 1, mas inicia o formulário 2)

Além disso, n / k = a e, como mencionado acima, a é um valor de i, então n> a> 1.

Portanto, a e k são números inteiros entre 1 e n (exclusivo). Como i alcança todos os números inteiros desse intervalo, em alguma iteração i = a e em outra iteração i = k. Se o teste de primalidade de n falhar por min (a, k), também falhará por max (a, k). Portanto, precisamos verificar apenas um desses dois casos, a menos que min (a, k) = max (a, k) (onde duas verificações se reduzam a um), ou seja, a = k, no qual a * a = n, que implica a = sqrt (n).

Em outras palavras, se o teste de primalidade de n falhar em alguns i> = sqrt (n) (ou seja, max (a, k)), também falhará em alguns i <= n (ou seja, min (a , k)). Portanto, seria suficiente se executarmos o teste de i = 2 para sqrt (n).

Aroonalok
fonte
Há muito mais curto e IMHO muito mais fácil de entender e explicações mais sobre-topic nos comentários e as respostas 6 anos de idade ...
Thierry Lathuille