Algoritimo para Numeros Primos [C++]

Assuntos Gerais
#1

Fala galera…

Estou precisando de uma ajudinha no meu trabalho de logica e matematica de programação

Estou precisando especifamente resolver esse problema: “Escreva um algoritimo que imprima todos os numeros primos existentes entre N1 e N2 que são numeros naturais fornecidos pelos usuários, deixando o código com o maior número de comentários possíveis para explicar o procedimento.”

Ou seja, o usuario entra com os dois valores, entao os numeros entre eles o algoritimo deverá calcular todos os numeros que sao primos (que sao aqueles divididos por dois numeros somente, por 1 e por ele mesmo)

O professor deu a dica de usar o loop for, e o bool (Esse é facultativo, pode usar ou não essa função)

Qualquer ajuda é bem vinda.

#2

O que você já fez?

#3

Procura o algoritmo de Fermat. Não vai ter uma boa performance, mas a implementação é trivial, e se baseia justamente em loops.

#4

uai tenta escrever um código ai que nós te ajudamos… mas primeiro você precisa escrever algo né. È bem simples isso ai se for para um intervalo pequeno e de números pequenos.

Abraço.

#5

Use o crivo de Eratóstenes. Ele é razoavelmente simples de implementar.

Se você procurar no Google por “crivo de Eratóstenes” ou “sieve of eratosthenes” é relativamente fácil encontrar implementações desse algoritmo.

#6

[quote=enantiomero]Use o crivo de Eratóstenes. Ele é razoavelmente simples de implementar.

Se você procurar no Google por “crivo de Eratóstenes” ou “sieve of eratosthenes” é relativamente fácil encontrar implementações desse algoritmo.

[/quote]

Pro seu problema, o crivo pode ser melhor mesmo. O teorema de Fermat é mais fácil, dá pra implementar em 4 linhas, mas você vai ter que testar cada número no intervalo.
Eu não lembro qual dos teoremas de Fermat que é (o pequeno, o último, etc), é aquele que diz que se um o módulo de um certo produto por um número p for igual a 2, p é primo. Eu tenho uma implementação dele aqui, em Java (que usa as tais 4 linhas). Se quiser, coloca aí o que você já fez que eu vou te ajudando.

#7

http://pt.wikipedia.org/wiki/Teste_de_primalidade_de_Fermat - é isto aqui? Isso exige usar o método BigInteger.modPow para primos nem tão grandes assim.

Fazer o teste de primalidade dessa maneira é adequado quando você quer checar se um dado número é primo, mas quando você tem uma sequência de números usar o crivo é mais rápido.

O problema do “pequeno teorema de Fermat” é que ele diz se um número é composto, mas não afirma categoricamente se um número é primo. Por exemplo, 1105 (que é claramente divisível por 5) é considerado como primo se você usar “a” = 2.

import java.math.BigInteger;


class TestePrimalidadeFermat {
    public static boolean fermatPrimalityTest (long n) {
        return BigInteger.valueOf(2).modPow (BigInteger.valueOf(n - 1), BigInteger.valueOf(n)).equals(BigInteger.ONE);
    }
    public static boolean fermatPrimalityTest (long a, long n) {
        return BigInteger.valueOf(a).modPow (BigInteger.valueOf(n - 1), BigInteger.valueOf(n)).equals(BigInteger.ONE);
    }
    public static void main(String[] args) {
        // Positive tests
        System.out.println (fermatPrimalityTest (13));
        System.out.println (fermatPrimalityTest (2147483647L));
        System.out.println (fermatPrimalityTest (2971215073L));
        // Negative tests
        System.out.println (fermatPrimalityTest (600851475147L));
        // Atenção, os "pseudo-primos de Fermat" falham neste teste.
        System.out.println (fermatPrimalityTest (1105L)); // veja em http://mathworld.wolfram.com/FermatPseudoprime.html
        // Portanto, se realmente você quer saber se um número é primo, você precisa variar os valores de a.
        // Para cada valor de "a", sendo "a" primo, a probabilidade de um número ser composto sendo que 
        // passa pelo teste de primalidade de Fermat diminui.
        System.out.println (fermatPrimalityTest (13, 1105L)); // imprime "false" porque não é um pseudoprimo de Fermat para a = 13.
    }
}
#8

[quote=enantiomero]
Fazer o teste de primalidade dessa maneira é adequado quando você quer checar se um dado número é primo, mas quando você tem uma sequência de números usar o crivo é mais rápido.
[/code][/quote]

Calma, cara. O tópico está aberto pra todos que querem ajudar, e não acho que ter mais de uma opção de implementação prejudique o autor do tópico, pelo contrário permite a ele escolher qual ele deseja usar. Se você não notou, no meu segundo post eu falo que o crivo pode ser melhor pro problema do cara. Além disso, a minha implementação do teorema de Fermat não usa BigInteger, nem reconhece 1105 como primo. Eu fiz a minha própria implementação, não procurei no Google.

#9