Qual o melhor modo de testar se um número é primo?

Olá
Tem esse link, agora não sei qto mais rápido ele é, pelo
que vi ele busca todos os primos…

Espero ter ajudado
Flwssss

Teve uma discussão sobre isso a pouco tempo neste fórum:
http://www.guj.com.br/posts/list/124189.java#671342

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)

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= 1060

Este método deve ser um pouco mais rápido:

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.

O crivo de Eratóstenes funciona de forma eficiente para números primos menores que 10 milhões.

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)

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= 1060

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.

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.

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.

De novo, vou mostrar o resultado pra você conferir se é isso mesmo.

A soma dos primos de 0 até 2.000.000 é 142.913.828.922 (use um long para fazer a totalização; esse número estoura um int).

Pela sua definição, 1 não é primo nem não-primo e não será considerado na somatória.

deu não!
usei o método de erastoteles e ficou em 999998000002

olha ai:

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);
    }
}

Teste sua rotina para n = 10 e n = 100, para ver se dá 17 ou 1020, conforme você mesmo postou.

Dica: você não copiou direito meu programa. Veja o que você fez no “while”.

E de qualquer maneira o grego chato que inventou o tal método é Eratóstenes, não Erastoteles (ele não é um mestiço de Aristóteles e Eros).

tem algo errado?

minha rotina....

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);
        
    }
}

foda q é lento para KCTs ahuahuahu.....

no momento esta em 257353: [telefone removido]

o inicio deu isso

2: 2
3: 5
5: 10
7: 17
11: 28
13: 41
17: 58
19: 77
23: 100
29: 129
31: 160
37: 197
41: 238
43: 281
47: 328
53: 381
59: 440
61: 501
67: 568
71: 639
73: 712
79: 791
83: 874
89: 963
97: 1060
101: 1161

Ops! Saquei malz ae
troquei a raiz do numero por 2

Salve Eratosrenes em!
Mas fiquei sabendo de um método ainda mais rápido que utilizava o método de Eratostenes e de outro matemático acho que francês.

Sei q tem uma parte que se pega o resultado do numero dividido por 66.

passado o primeiro milhão… vamo em…

1.024.951: 39.406.066.834 1.024.957: 39.407.091.791 1.024.963: 39.408.116.754

Lavieri esse seu método é muito lento e exige muito da máquina! é melhor ficar com o do Grego chato.
Simples e útil!

uhuhuh acabou agora da forma tradicional ^^

1999957: 142907828981 1999969: 142909828950 1999979: 142911828929 1999993: 142913828922 142913828922

init:
deps-jar:
Compiling 1 source file to C:\Users\Administrador\Documents\NetBeansProjects\GujForunsTest\build\classes
compile-single:
run-single:
142913828922
CONSTRUÍDO COM SUCESSO (tempo total: 1 segundo)

posta o teu código… aki o meu demorou mais o.O, com o Crivo

public static final int[] primos = new int[1000000];
    public static int next = 0;

    public static boolean isPrimoOptimizade(int numero) {
        if (numero < 2)
            return false;
        int count = 0;
        while(primos[count] != 0 && //ou seja não há mais primos a testar
                     primos[count]*2 <= numero) { //com certeza não é divisivel pelos proximos primos...
            if (numero%primos[count] == 0)
                return false;
            count++;
        } 
        primos[next++] = numero;
        //System.out.println("primos["+next+"] = " + numero);
        return true;
    }

    public static void main(String ... args) {
        long soma = 0;
        for (int i = 0; i <= 2000000; i++)
            if (isPrimoOptimizade(i)) {
                soma += i;
                //System.out.println(i + ": " + soma);
            }
        System.out.println(soma);
     }

run:
142913828922
CONSTRUÍDO COM SUCESSO (tempo total: 1 minuto 40 segundos)

http://www.hinduonnet.com/fline/fl1917/19171290.htm

agora vi o erro!!

troque essa linha

while(primos[count] != 0 && //ou seja não há mais primos a testar primos[count] <= (int)Math.sqrt(numero)) { //com certeza não é divisivel pelos proximos primos...

agora foi em 1s

ai sabe como eu posso herdar todas as declarações de um método para um outro método que estão na mesma classe?

e sim, DavidUser, da pra ser mais eficiente ainda… so precisa testar os números impares… os pares já são primos…

então no lugar de incrementar o teste de 1 em 1… so iniciar do 3, e testar de 2 em 2