Eu peguei esse código no site do MIT e eu achei legal e queria entender melhor como ele funciona. O funcionamento básico eu entendi, mas tem uns detalhes que eu queria saber.
Então eu resolvi fazer um Estudo Rápido, para analisar e entender o código. Quem puder me ajudar eu agradeço!
Para esclarecer: número primo é todo número divisível apenas por 1 e por ele mesmo. Exemplos: 2, 3, 5, 7, 11 (eu poderia ir até 999.983: calculei com esse programa, hahaha )
O código do programa é o seguinte:
public class Primes
{
public static void main(String[] args)
{
int nValues = 50;
boolean isPrime = true;
for(int i = 2; i <= nValues; i++)
//a condição é imprimir todos os primos menores ou iguais a 'nValues'
{
isPrime = true;
for(int j = 2; j < i; j++)
{
if (i % j == 0)
//aqui a verificação é se i é divisível por j
//se for, o número não é primo, pois j é igual a 2
//e um número só é primo se for divisível por 1 e
//por ele mesmo
//ou seja, se a divisão de i por j tiver resto igual a
//zero, ele é divisível por j
{
isPrime = false;//se não for primo
break; //não é exibido
}
}
if (isPrime)//se for primo o número é exibido
System.out.println(i);
}
}
}
Os comentários são meus, mas algumas coisas eu não entendi, por exemplo:
No primeiro for, porque a variável booleana isPrime é definida novamente, ela já não foi criada com esse valor?
No segundo for, a condição para execução do loop é "(int j = 2; j < i; j++)", ou seja, enquanto j for menor que i, certo? Ou essa condição quer dizer outra coisa?
A verificação para saber se um número é primo pode ser ver se ele é divisível por 2. Se for ele não é primo. Se não for ele é primo. Mas então, porque j precisa ser incrementado?
(i % j == 0) Essa parte do código (a condição do primeiro if), significa: resto da divisão de i por j igual a 0, certo?
São essas minhas dúvidas. Achei bem legal esse programa, eu dei uma incrementada nele e fiz um que copia a lista dos números para um arquivo ‘.txt’. Eu fiz isso porque quando eu calculei uma lista de primos até 100.000, o prompt não mostrava todos.
O primeiro for vai de 2 até 50 verificando se cada número é primo ou não. Quando acontece do número não ser primo , a varíavel isPrime é definida como false.
Ao reiniciar o for a variável isPrime terá o valor false , então o algoritmo faz isPrime=true para garantir que o loop anterior não interfira no atual.
Pense que se não houvesse a instrução isPrime=true, quando o loop chegasse ao número 11 que é primo, a variável isPrime estaria definida como false pois o número anterior (10) não é primo, entao o algoritmo não imprimiria 11 na tela , pois, isPrime está definida como false.
A verificação para saber se um número é primo pode ser ver se ele é divisível por 2. Se for ele não é primo. Se não for ele é primo. Mas então, porque j precisa ser incrementado?
Primeiro que para saber se um número é primo não é ver se se ele é divisivel por 2, com isso vc só pode afirmar se ele é par ou impar, para saber se um número é primo tens que tentar dividi-lo por todos os números menores que ele, por isso que o j é incrementado até que seja divisivel ou até que j seja igual ao número testado.
Da uma olhada nos seguintes algorítmos para saber mais sobre o assunto: crivo de eratóstenes, teste de primalidade probalistico lucas-lemmer, fatoração por Fermat, Euler, crivo quadrático, number field sieve e método de frações continuadas.
elinton, eu entendi o que você falou, mas eu acho que esse jeito que eu falei também está certo. Olha:
4 é divisível por 2, resto = 0.
5 não é divisível por 2, resto = 1.
4 não é primo, 5 é primo.
Então se você pegar um número primo e dividi-lo por 2, o resto não vai ser igual a 0. Só não vale para o 2, que é divisível por 2 e também por 1 e por ele mesmo (ou seja: 2)
O que eu entendi do código é que ele usa o operador % para ver se o resto da divisão é igual a 0. Sendo igual, isso significa que ele é divisível por 2, então não é primo.
Eu entendi isso: para verificar se um número é um primo não precisa dividi-lo por todos menores que ele. Se ele for divisível por 2 é o suficiente para dizer que ele é primo.
Acabei de dar uma modificada no código para ver se entendia isso. Eu vi que os números que não são primos são os i com valores: 4,6,8,9,10,12,14,15,16…
Assim, o j serve para ver se o número é divisível por 2 ou por 3. Eu escrevi para mostrar o valor do i não primo e o valor de j quando o número não é primo. A saída foi assim:
[quote]2
3
i = 4, j=2
5
i = 6, j=2
7
i = 8, j=2
i = 9, j=3
i = 10, j=2
11
i = 12, j=2
13
i = 14, j=2
i = 15, j=3
i = 16, j=2
17[/quote]
Então, no fim eu acho que a verificação é:
É divisível por 2? É -> não é primo.
É divisível por 2? Não -> j+1 -> É divisível por 3? É -> não é primo.
É divisível por 2? Não -> j+1 -> É divisível por 3? Não -> é primo.
Então , o que é importante saber sobre os números primos é que eles somente são divisíveis por 1 e por eles mesmos. Esta é a definição.
Sobre a variável j
Ela inicialemente recebe o valor 2, que é o valor que deve começar a ser usado como divisor pois o número 1 pode dividir um número primo segundo a definição.
Agora a variável j , tem de ser incrementada até alcançar o valor i-1, pois a definição diz que um número primo deve pode ser dividido por ele mesmo.
Então vamos analizar:
i está em 10
//Este for vai testar todos os divisores de 2 até 9
for(j=2 ; j < 10 ; j++)
{
//10 é divisível por 2-3-4-5-6-7-8-9 ???
if(i%j == 0)
{
não é primo
}
}
Os números primos são necessários nas grandes tabelas hash e em criptografia entre outras aplicações. O método sugerido seria muito lento em muitos casos práticos. Por este motivo o Louds sugeriu o estudo de diversos algoritmos para melhor avaliar o que melhor se aplicaria em cada caso.
Mas, jandisson, é isso realmente o que esse programa faz? Ele verifica se o número atual é divisível por todos os anteriores? Eu entendi, era o que o elinton falou, eu até fiquei tentando ver se era mesmo só 2 e 3, mas não, não tem como ser.
Os números primos são divisíveis somente por 1 e por eles mesmo. Certo. Mas se nós pegarmos qualquer número e fizermos duas afirmações:
P = resto da divisão por 2 é diferente de zero
Q = resto da divisão de 3 é diferente de zero
Se, e somente se, P e Q forem verdadeiros, o número é primo. Se ele for divisível por 2, não é primo. Se for divisível por 3, não é primo. Só que quando eu faço isso, o 2 e o 3 ficam de fora, pois eles são divisíveis por 2 e por 3, respectivamente. Eu pensei nesse algoritmo, mas precisaria melhorar, vou dar uma estudada nisso, tentar fazer um código assim.
Olha que com esse programa eu calculei os números primos até 999.983. É estranho porque, quando ele chegou no número 900.000 ele fez a divisão e verificou o resto com todos os números anteriores? É uma coisa meio lenta mesmo. O programa demorou alguns minutos (uns 10 ou 15 acho) para ser executado.
É, Luca, se fosse rodar esse algoritmo para grandes aplicações imagino que seria muito lento. Vou estudar esses que o Louds falou e ver se eu consigo fazer um que seja um pouco melhor.
Só tenho mais uma pergunta: o break; pára o segundo loop e retorna para o primeiro ou pára o segundo e retorna para o segundo?
Ah, me liguei agora! Nossa, eu calculei os primos, mostrando as variáveis i e j, mesmo para os não-primos. E tem uns que são divisíveis por 11, como o 121, por exemplo. E aí ele não é divisível por 2, nem por 3, mas não é primo. Então aquilo que eu estava falando está errado! Entendi agora!
Precisa ir adicionando um no j até chegar em um que seja divisível. Elinton entendi o que vc disse agora, cara!
Eu concordo com o Luca quando diz que o código é muito simples e lento para algumas finalidades mas , a minha inteção era somente demostrar o funcionamento do algoritmo para que o nosso amigo pudesse entender… nào disse que o código é rápido.
Está certo zirocool, eu não estava confundindo com pares e ímpares. Eu até disse no meu primeiro post:
O que aconteceu foi que eu achei que para verificar se um número era primo bastava ver se ele era divisível por 2 ou por 3. Mas depois eu entendi que não é isso, pois tem números que não são divisíveis por 2 nem por 3 e que não são primos, como é o caso do 25. Tem que ir testando até chegar no 5, aí confirma que ele não é primo.
inclusive é um dos grande enigmas matemático achar uma formula simples que calcule se um numero é ou não um numero primo!!!
Os numeros primos estão presentes em diversas operações, em bancos, sistemas de segurança!!se descobrir um algoritmo de eficiência muito boa…muitos sistemas baseados em criptografia estariam em risco…
CUIDAAAADO!
Hahahaha! Sério mesmo? A segurança de operações bancárias é baseada em números primos? Mas como que um algoritmo simples para saber se o número é primo ou não pode afetar sistemas baseados em criptografia?
Uma das aplicações de números primos é o uso nas chaves públicas de criptografia. Se o números primos não forem gerados de forma correta, a segurança da chave poderá ficar comprometida.
Dê uma googlada que perceberá a importância de conhecer bons algoritmos para gerar números primos, principalmente se você precisa usar criptografia ou armazenar dados em tabelas hash.
Se reside no fato de que é computacionalmente barato gerar um número muito grande, mas é praticamente impossível (com o anteparo computacional que temos hoje) decompor esse número em seus fatores primos.
Há tanta confiança nesse fato que a criptografia hoje é quase toda ela baseada em números primos. O RSA, por exemplo, se baseia no fato de que é fácil calcular um produto n a partir de dois números primos muito grandes p e q, mas é quase impossível achar p e q fatorando n, já que não há um jeito barato de decompor números enormes
Descobrir a primalidade de um número não faz tanta diferença assim pra criptografia, até existe algoritmo eficiente pra isso, o que realmente importa é achar os fatores de um número.
Achar numeros primos ou verificar a primalidade de um numero naum compromete sistemas de segurança. Hoje ja existe um algoritmo em tempo polimonial q verifica a primalidade de um numero com 100% de eficacia eh o algoritmo de AKS, o RSA tinha uma margem de erro, infima mas tinha.
Pra comprometer os sistemas de criptografia soh se acharem um algoritmo rápido pra fatorar un numero. No futuro o q pode comprometer mais os sistemas de criptografia são os computadores quanticos, já existe um algoritmo eficiente pra fatoração em CQ, o problema e manter o sistema estavél ah tempo de fatorar o numero.
)