Arquivo Discussoes de Programacao e Tecnologia 
Galera,
Estou com uma dúvida um tanto quanto “idiota”…mas estou resolvendo uma série de exercícios durante as férias e não sei se por cansaço não estou conseguindo pensar em uma solução SIMPLES para o problema abaixo:
10 ? Desenvolva um programa que dado um número inteiro o programa
informe se o mesmo é um número primo
Desde já agradeço pela colaboração de todos.
boolean ehPrimo = true;
for (int i = 3; i < seuNumero; i++) { //Acho q começa a checar com 3, né?
if (seuNumero % i == 0) {
ehPrimo = false;
break;
}
}
[]´s
boolean ehPrimo = true; for (int i = 3; i < seuNumero; i++) { //Acho q começa a checar com 3, né? if (seuNumero % i == 0) { ehPrimo = false; break; } }[]´s
Esse é o mais basicão mesmo. Outras formas de melhorar:
E muito mais. Procure por teste de primalidade no google.
Então, uma vez fiz um programinha que precisava verificar primaridade de uns números.
Na época programava em C++ (nem sinto tanta saudade…) fiz algo semelhante.
Mas talvez seja o caso de verificar o resto com 2 (caso o numero seja parte) e dai por diante começar pulando de 2 em 2 numeros a partir do 3, verificando apenas pelos impares.
Não acredito que seja uma solução muito performática, mas ao menos um pouco melhoradinha, já que não checa tudo… imagine se verificar o numero 1398129387129381723897123 que beleza de loop que teremos.
Ok, exemplo exagerado, mas pegaram o que quis dizer.
Ou também se ele verificar apenas os numeros que são divisiveis por 1 e por ele mesmo!
Sim, essa é a definição de números primos.
Mas como sugere que se faça essa verificação?
A sugestão acima divide o número em questão por todos os números a partir de 2 (ou 3) até ele e verifica o resto dessa divisão, caso em algum momento esse resto seja igual a 0, quer dizer que ele não é primo.
boolean ehPrimo = true; for (int i = 3; i < seuNumero; i++) { //Acho q começa a checar com 3, né? if (seuNumero % i == 0) { ehPrimo = false; break; } }[]´s
boolean ehPrimo = true; for (int i = 3; i < seuNumero; i++) { //Acho q começa a checar com 3, né? if (seuNumero % i == 0) { ehPrimo = false; break; } }[]´s
Esse é o mais basicão mesmo. Outras formas de melhorar:
- Contar de dois em dois
- Contar até a raiz quadrada do número pesquisado
- Guardar todos os números primos encontrados, e dividir por eles.
E muito mais. Procure por teste de primalidade no google.
Em ordem crescente, os primeiros números primos são: 2, 3, 5, 7, 11, 13, 17, 19, …
Por convenção, 1 não é considerado um número primo. Uma razão, é o fato de que isto possibilita-nos estabelecer proposições sobre os números primos, sem introduzir qualificações.
Então, deve-se começar no 2, e não no 3.
Se ele for divisivel por 1 o resultado será ele mesmo, se for divisivel por ele mesmo o resultado será 1, mudando um pouquinho essa implementação que vc fez ai em cima vc resolve isso.
Que tal, para começarmos:
public static boolean isPrimo(int num) {
if (num < 2) {
return false;
}
if (num == 2) {
return true;
}
if ((num & 1) == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(i); i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
long inicio = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
if (isPrimo(i)) {
System.out.println(i);
}
}
System.out.printf("Tempo gasto: %d ms%n",
(System.currentTimeMillis() - inicio));
}
Então, deve-se começar no 2, e não no 3.
E se fosse algo como:
é 2 ou 3? Se sim - é primo.
senão
é par? Se sim - não é primo (numero %2)
Se não - tente até n/2 encontrar primos que sejam divisores.
Uma estratégia interessante (e simples) é a do crivo de eratóstenes
Então, deve-se começar no 2, e não no 3.E se fosse algo como:
é 2 ou 3? Se sim - é primo.
senão
é par? Se sim - não é primo (numero %2)
Se não - tente até n/2 encontrar primos que sejam divisores.Uma estratégia interessante (e simples) é a do crivo de eratóstenes
http://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes
Só trocaria o n/2 pela raiz quadrada de n.
Então, deve-se começar no 2, e não no 3.E se fosse algo como:
é 2 ou 3? Se sim - é primo.
senão
é par? Se sim - não é primo (numero %2)
Se não - tente até n/2 encontrar primos que sejam divisores.
Até a raiz quadrada de n. É por que não existem divisores de um número maiores que raiz quadrada dele. Então se você não achou nenhum divisor até aí, ele é um número primo.
Eu já acho que estamos esquentando demais a cabeça por algo que parece ser um simples probleminha de faculdade =P
[]´s
Só trocaria o n/2 pela raiz quadrada de n.
Perfeito Tchello! O ideal é raiz quadrada mesmo.
Uma estratégia interessante (e simples) é a do crivo de eratóstenes
http://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes
Eu já acho que estamos esquentando demais a cabeça por algo que parece ser um simples probleminha de faculdade =P[]´s
Pô, mas o “simples probleminha” de lidar com números primos rende até um prêmio batendo na casa de milhão de reais, fora as aplicações dos números primos.
Mas de fato o original era um problema de faculdade
Só para constar: o algoritmo do Crivo em Java está um lixo. Vou melhorá-lo.
BOA! só o i*i<tamanho mostrou que performance não era relevante para quem escreveu.
Só para constar: o algoritmo do Crivo em Java está um lixo. Vou melhorá-lo.BOA! só o i*i<tamanho mostrou que performance não era relevante para quem escreveu.
Eu já acho que estamos esquentando demais a cabeça por algo que parece ser um simples probleminha de faculdade =P[]´s
Pô, mas o “simples probleminha” de lidar com números primos rende até um prêmio batendo na casa de milhão de reais, fora as aplicações dos números primos.
Mas de fato o original era um problema de faculdade
Prêmio?? Que prêmio?
[]´s
A Eletronic Frontier Foundation tem prêmios de 150 mil e 200 mil dólares para quem descobrir um número primo com pelo menos 100 milhões e 1 bilhão de dígitos decimais.
Santa falta do que fazer com dinheiro, Batman!
=P
Santa falta do que fazer com dinheiro, Batman!
=P
Isso na verdade é investir o dinheiro. A base da criptografia são os números primos. Imagine quebrar uma senha (o qualquer outra coisa) que foi criptografada a partir de um número primo de 100 milhões de dígitos na força bruta :shock:
Para esse pessoal um número giganorme desse tem aplicação (senão nem pagariam essa grana toda por um número).
PS: O algoritmo do Crivo na Wikipédia foi (bem) melhorado.