números primos[finalizado]

[Mauricio1993]

[quote=entanglement]Alguém está tentando ensinar você que um número é primo se ele não for divisível por 2 ou por 3. Conforme você viu, 5 já dá problemas porque é primo.

Se você for nessa onda, então teste contra os seguintes números, se você quer saber se os números entre 1 e 15000 são primos:

2 , 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113

Se um número não for divisível por nenhum desses números acima, e se ele estiver abaixo de 16128, então ele é primo. (Isso é verdade mesmo).

Só que você viu que isso é meio esquisito, não?

Se por acaso você tentar o algoritmo com o número 16129, que não é primo (na verdade ele é 127 x 127), o seu algoritmo já indicará um resultado incorreto.
[/quote]

tbm é verdade, pois no livro que eu vi isso, dizia explicitamente que não servia para todos os numeros. se eu não me engano eram os números até 100, eu acho, tem mto tempo q eu li o tal livro.

isso apresenta mtas falhas, mas calma, é só minha 1° aula, eu vo estudar mais

[Beibin]

Teorema de Wilson.

Dado um número p, se (p - 1)! + 1 mod p = 0, o número é primo.

[code]boolean isPrime(long p) {
if ((fatorial(p - 1) + 1) % p == 0) return true;
return false;
}

long fatorial(long n) {
if (n <= 1L) return 1;
else return n * fatorial(n - 1); // Fatorial recursivo…
}[/code]

Não é o algoritmo mais eficiente, mas funciona.

Há um problema com essa implementação, por parte do fatorial. Número muito grande para o tipo de dado.

Funciona corretamente para p <= 19. Uma implementação utilizando BigInteger deve funcionar perfeitamente com qualquer número.

[dina]

tá certa sim, só que os primos tem de retornar os restos diferentes de zero(to procurando o simbolo pra isso…)

O símbolo para saber o resto de uma divisão é %
8%2 = 0 (o resto é 0)
9%2 = 1 (o resto é 1)

[tkx]

Pessoal, e principalmente Mauricio1993:
Como vc disse q eh iniciante, está “aprendendo” Java, provavelmente o que o seu professor quer é treinar estruturas de repetição aninhadas e lógica de programação.
A definição de número primo é:
Um número natural, que possua exatamente dois divisores: 1 e ele mesmo!
Como é natural, deve ser um número inteiro não-negativo, ou seja, de 0 acima.
0 não é primo, pq eh divisível somente por 1 (0/0 é indeterminado)
1 tb não é, pq é divisível por 1, ou por ele mesmo, ou seja, só tem 1 divisor!
2 é primo, e é o único par primo! divisível somente por 1 e ele mesmo!

Seguindo esta lógica, como saber se 2101 é primo?

Há diversos teoremas e formas, como muitos já falaram, mas como vc está iniciando, vai fazer na força bruta mesmo!
Seja x o numero a testar,
x%(x-1)!=0
x%(x-2)!=0
x%(x-3)!=0
x%(x-4)!=0
(…)
x%2!=0

Se tudo isso for != 0, é primo! senão, não é!
Mas como fazer isso? com um for (como propus anteriormente)

Acredito que seu problema não esteja na programação, nem no Java, e sim na definição de número primo!

Qualquer dúvida tamus aki!

[Mauricio1993]

então. foi justamente isso que ele me disse. Que se um numero primo é um número q só tem 2 divisores (ele mesmo e 1) então com 3 comandos de divisão eu poderia achar ele. e também me disse que uma forma de se fazer era usando o comando if, mas eu não tenho certeza de COMO implementar esses comandos, dai me lembrei do tal livro. quase deu certo, mas definitivamente a precisão de tal coisa é deplorável.

de qualquer jeito eu vo ver o que dá pra ser feito, e vo testa o código que tu propos.

só não sei se vo pode faze isso hj, por causa das aulas (ensino médio) que logo logo tão me tirando de casa.
qualquer coisa eu faço de madru e posto amanhã cedo

[adriano_si]

meus 2 centavos:

public class CrivoEratostenes {
	
	public static void main(String[] args) {
		List<Integer> primos = new ArrayList<Integer>();
		List<Integer> removidos = new ArrayList<Integer>();
		StringBuilder resultado = new StringBuilder("Primos: ");
		
		int qtd = Integer.parseInt(JOptionPane.showInputDialog("Entre com o Nº máximo a ser verificado:"));
		
		Long time1 = System.currentTimeMillis();
		
		for(int i = 2; i <= qtd; i++){
			primos.add(i);				
		}
		
		removidos.addAll(primos);
		
		for(Integer primo : primos){
			if(primo == 2 || primo == 3 || primo ==5) continue;
			if(primo%2 == 0){ removidos.remove(primo); }
			if(primo%3 == 0 && removidos.contains(primo)){ removidos.remove(primo); }
			if(primo%5 == 0 && removidos.contains(primo)){ removidos.remove(primo); }
		}
				
		for(Integer primoRes : removidos){
			resultado.append(primoRes + ", ");
		}
		
		System.out.print(resultado.deleteCharAt(resultado.length()-2));
		
		Long time2 = System.currentTimeMillis();
		System.out.println("Tempo de execução: " + (time2 - time1) + " ms");
	}
}

Coloquei o temporizador só pra ver se não iria ficar lento demais e validar a eficácia do código…

Abs []

[entanglement]

meus 2 centavos:

Credo, não pensei que você também era da mesma religião que acredita que qualquer número que não seja divisível por 2, 3 e 5 é primo.

Essa religião é do mal; não é a mesma que acreditava que o número pi era exatamente igual a 3, porque depois ela se corrigiu.

Hurã fez um tanque redondo de bronze, com dois metros e vinte de profundidade, quatro metros e quarenta de diâmetro e treze metros e vinte de circunferência.

49 é primo?

[adriano_si]

[quote=entanglement][quote=adriano_si]
meus 2 centavos:
[/quote]

Credo, não pensei que você também era da mesma religião que acredita que qualquer número que não seja divisível por 2, 3 e 5 é primo.

Essa religião é do mal; não é a mesma que acreditava que o número pi era exatamente igual a 3, porque depois ela se corrigiu.

Hurã fez um tanque redondo de bronze, com dois metros e vinte de profundidade, quatro metros e quarenta de diâmetro e treze metros e vinte de circunferência.

49 é primo?
[/quote]

Cara… PQP… quase me enterrei de vergonha. Lí a merda do algoritmo e implementei de forma IDIOTA… tbm, peguei pra fazer em paralelo com a geração de uma versão para a Produção aqui no trampo… se tu não falasse, eu ia passar lotado… CARACAAAAAAAAAAAAAAAAA que coisa mais idiota… Não responderei mais com pressa aqui no fórum…

Segue meus 3 centavos agora… Espero que não tenha deixado escapar nada dessa vez… testei com valor 30 e testei com valor 100…

public class CrivoEratostenes {
	
	public static void main(String[] args) {
		List<Integer> primos = new ArrayList<Integer>();
		List<Integer> removidos = new ArrayList<Integer>();
		StringBuilder resultado = new StringBuilder("Primos: ");
		
		Integer qtd = Integer.parseInt(JOptionPane.showInputDialog("Entre com o Nº máximo a ser verificado:"));
		
		int baseVerificacao = (int)Math.sqrt(qtd.doubleValue()); 
		
		for(int i = 2; i <= qtd; i++){
			System.out.println("Adicionando: " + i);
			primos.add(i);				
		}
		
		removidos.addAll(primos);
		
		int base = 0;
		int contBase = 0;
		System.out.println("Removendo Multiplos...");
		
		while(base <= baseVerificacao){
			base = removidos.get(contBase);
			for(Integer primo : primos){
				if(primo != base && primo%base == 0){
					System.out.println("Remover: {" + primo + "} Base: " + base);
					removidos.remove(primo);
				}
			}
			primos = new ArrayList<Integer>(removidos);
			contBase++;
		}
		
		System.out.println("Resultado: ");
		for(Integer primoRes : removidos){
			resultado.append(primoRes + ", ");
		}
		
		System.out.print(resultado.deleteCharAt(resultado.length()-2));
		
	}
}

E respondendo… não, 49 não é primo… rsrs

PQP… fods mesmo… fiquei pra baixo com essa…

[entanglement]

Não tem problema. Só lembrar que “remove” é uma operação lenta em um ArrayList, ainda mais que você está usando a versão que remove por objeto - ele tem de procurar no array inteiro até encontrar. Alguém aqui no GUJ implementou usando um BitSet - que tal dar uma olhada nessa versão?

http://www.guj.com.br/posts/list/43972.java#233496

[adriano_si]

tô por dentro… hueheueheueheuehu fiz o mais prático só pra redimir a cagada anterior…

Não conheço bem o BitSet… mas vou dar uma olhada…

abs []