Sou novo no GUJ e novo nesse mundo de linguagem java,
Então muito bem, eu gostaria que alguém me ajudasse com essa atividade aqui:
Crie um número inteiro e verifique se ele é primo.
Eu queria um código com for será que é possível?
Java (verificar números primos)
J
13 Respostas
E
Procure aqui no GUJ, tem um monte de código pronto, você pode tentar entender o código.
No Google, digite:
primos site:guj.com.br
Vai achar várias coisas interessantes
J
Eu já tinha procurado mas não tinha achado nada, mas agora eu encontrei valeu
Seguindo essa linha, entanglement,
Você confia nos métodos que implementam técnicas de “probablePrime” ou prefere utilizar métodos mais concretos?
E
Se for para checar se um determinado número muito grande talvez seja primo e não está realmente querendo saber se é realmente (100% de certeza) que é primo, normalmente probablePrime é suficiente.
Se for para resolver um daqueles problemas do Project Euler, normalmente você precisa de uma tabela grande de primos, então é melhor calcular uma tabela com o Crivo de Eratóstenes ou outro crivo da sua escolha.
Nossa, não conhecia esse Crivo de Eratóstenes (ou nenhum outro Crivo, aliás).
Descobri que os meus algoritmos do ProjectEuler são muito mais “brute force” do que eu imaginava 
Só pra deixar um exemplo no post, fiz um exemplo de implementação do Crivo de Eratóstenes.
public class Crivo{
public static void main(String[] args){
System.out.println(crivo(120));
}
public static List<Integer> crivo(int max){
List<Integer> list = createList(max);
int limitCheck = (int) Math.round(Math.sqrt(max));
for(int i=2 ; i<limitCheck ; i++){
removeMultiples(list, i);
}
return list;
}
private static List<Integer> createList(int max){
List<Integer> list = new ArrayList<Integer>(max-2);
for(int i=2 ; i<max ; i++){
list.add(i);
}
return list;
}
private static void removeMultiples(List<Integer> list, int i){
Iterator<Integer> ite = list.iterator();
while(ite.hasNext()){
int num = ite.next();
if(num != i && num % i == 0){
ite.remove();
}
}
}
}
E
Faz 6 anos que o Thingol postou isto aqui.
import java.util.*;
class Sieve {
private BitSet bs;
private int n;
public Sieve (int n) {
this.n = n;
bs = new BitSet (n);
bs.flip (2, n - 1); // 1 é primo?
}
public BitSet sieve() {
int sqrtN = (int) Math.sqrt (n);
int j = 2;
while (j <= sqrtN) {
for (int i = j + j; i < n; i += j) {
bs.clear (i);
}
j = bs.nextSetBit (j+1);
}
return bs;
}
public static void main(String[] args) {
Sieve s = new Sieve(Integer.parseInt (args[0]));
long t = System.currentTimeMillis();
BitSet bs = s.sieve();
System.out.println (System.currentTimeMillis() - t);
System.out.println (bs.cardinality()); // números de primos entre 1 e n - 1
}
}
Um BitSet pode conter até 2 bilhões de elementos (gastando 1 bit por elemento, o que daria um tamanho máximo de memória de 256 MB, o que não é nada absurdo.
E
Fica como exercício modificar a solução do Thingol para suportar 4 bilhões de elementos (lembrando que os pares, exceto o número 2, não são primos). Para modificar o crivo para cada bit indicar apenas números ímpares não deve ser muito difícil.
E
Esqueci de mencionar que o BitSet retornado por essa classe do Thingol indica se um número n é primo se o elemento n estiver setado, e não é primo se o elemento n desse bitset não estiver setado.
Pessoal essa é lendária, quem nunca fez esse exercício de algoritmo que atire a primeira pedra.
Muito boa para quem vai começar a estudar programação básica e entender laços de repetição e estrutura condicional
Desafio: quero ver quem cria um código que não exija muito do processador para achar os 30 primeiros números perfeitos
Deixa eu ver se eu entendi. Esse BitSet verifica quantos primos existem dentro da faixa especificada, mas não guarda os números em si, correto?
Opa, então vamos a fonte dos desejos
http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html
E
Pessoal essa é lendária, quem nunca fez esse exercício de algoritmo que atire a primeira pedra.
Muito boa para quem vai começar a estudar programação básica e entender laços de repetição e estrutura condicional
Desafio: quero ver quem cria um código que não exija muito do processador para achar os 30 primeiros números perfeitos
O trigésimo número perfeito tem 79502 dígitos.
Uma forma trivial de ir listando os números perfeitos é recorrer à Wikipedia e saber que um número perfeito é da forma
2^(p-1) * (2^p - 1)
quando 2^p - 1 é primo (chamado “primo de Mersenne”).
Portanto, basta descobrir como achar os primos de Mersenne e calcular a expressão acima.
O problema então é outro: saber como um número de 39750 dígitos (que seria o trigésimo primo de Mersenne) é primo.
O crivo de Eratóstenes (com a otimização que indiquei) só acha os primos que têm até 9 dígitos - ou seja, com essa tabela de primos poderia determinar se um número de até 18 dígitos é primo.
Você pode usar aquele método “isProbablePrime” para saber se um número dado “pode ser primo”, mas para efeitos desse seu problema, você quer um número que é “primo de forma matematicamente provada”.
Criado 25 de outubro de 2012
Ultima resposta 26 de out. de 2012
Respostas 13
Participantes 4
Alura O que é Python? — um guia completo para iniciar nessa linguagem de programação Acesse agora o guia sobre Python e inicie sua jornada nessa linguagem de programação: o que é e para que serve, sua sintaxe e como iniciar nela!
Casa do Codigo Engenharia de Prompt para Devs: Um guia para aprender a... Por Ricardo Pupo Larguesa — Casa do Codigo