Gente meu objetivo era testar de 1 a 2 milhões quais são os primos então o objetivo é encontrar o modo mais rápido para a máquina processar julgando se o número é primo ou não meu método é esse:
public static boolean primos(long x){
int z=0;
boolean res;
for(long i=1;i<=x;i++)if((x%i)==0)z++;//adiciona o numero de divisores perfeitos para x
return((z==2)? true:false);//se é divisivel por apenas 2 números(é primo:1 e ele mesmo)retorna seu valor
}
Existe algum pacote que teste mais rápido pois do modo que estou fazendo vai demorar muito! pra terminar a execução! :?
:x
Não é o mesmo do outro tópico!
O problema é que aki eu não tenho que calcular os fatores primos mais tenho de somar todos os primos existentes de 1 a 2000000 exemplo com números menores:
de 1 a 10
2+3+5+7=17
se eu fizer a raiz do número a soma não sera a mesma olha:
de 1 a 100(a raiz se 100 é 10)
public static boolean primos(long x){
if (x == 1){ // 1 é caso especial, e não é primo
return false;
}
// sabemos que o 1 é divisor de todos os números, podemos começar a procurar no dois
// basta percorrer a lista até x/2. O máximo divisor que um número tem, sem ser ele próprio é a sua metade.
for(long i=2;i<=x/2;i++) {
if((x%i)==0) {
return false; //Assim que encontra um divisor, sabe que o número não é primo.
}
}
return true; //não encontrou divisores, o número é primo
}
Na verdade você já tem um algoritmo eficiente naquele outro tópico.
E só para corrigir o pmlm em questão da eficiência, quando estamos falando de números primos você pode começar pela raiz quadrada do número, não precisa ser da metade. O que torna o algoritmo realmente bastante eficiente.
[quote=DavidUser]Não é o mesmo do outro tópico!
O problema é que aki eu não tenho que calcular os fatores primos mais tenho de somar todos os primos existentes de 1 a 2000000 exemplo com números menores:
de 1 a 10
2+3+5+7=17
se eu fizer a raiz do número a soma não sera a mesma olha:
de 1 a 100(a raiz se 100 é 10)
O Bruno Bastos indicou o caminho correto: modifique o meu programa que acha os números primos, para poder calcular a soma.
Calcular essa soma de 1 até 2000000 vai levar cerca de 5 a 10 segundos, dependendo da velocidade do seu computador.
Não é necessário testar cada primo um por um; se fizer do jeito que você quer fazer, vai levar cerca de 10 a 15 horas, e isso não é legal.
[quote=BrunoBastos]Na verdade você já tem um algoritmo eficiente naquele outro tópico.
E só para corrigir o pmlm em questão da eficiência, quando estamos falando de números primos você pode começar pela raiz quadrada do número, não precisa ser da metade. O que torna o algoritmo realmente bastante eficiente.[/quote]
Dinovo!.. :x
se calulo os de 1 a 10: 2+3+5+7=17
ja os de 100 é bem diferente da muito mais intendeu! eu quero a soma de todos os primos entre eles.
public class p10 {
public BitSet bs;
public static void main(String[]args){
p10 s= new p10();
int num=2000000;//num é o valor final
long sum=0;
s.findprimes((int)num+1);
for(int i=2;i<=num-2;i++) if(s.isprime(i)==true)sum+=i;
System.out.println(sum);
}
//pelo método de erastoteles:
public void findprimes(int n){
bs = new BitSet(n+1);
int pz=(int)Math.sqrt(n);
bs.set(0, n);
int x=2;//primo inícial
while (x<=2){
for(int i=x+x;i<=n;i+=x)bs.clear(i);
x=bs.nextSetBit(x+1);
}
}
public boolean isprime(int n){
return bs.get(n);
}
}
[code]public class NumerosPrimos {
public static boolean isPrimo(int numero) {
if (numero < 2)
return false;
boolean result = true;
int metade = numero / 2;
for (int i = 2; i <= metade; i++) {
if (numero % i == 0) {
result = false;
break; //putz tinha eskecido o break ... restartei agora ta + rapido
}
}
return result;
}
public static void main(String ... args) {
long soma = 0;
for (int i = 0; i <= 2000000; i++)
if (isPrimo(i)) {
soma += i;
System.out.println(i + ": " + soma);
}
System.out.println(soma);
}
