Estudo Rápido: números primos

Programação Java
#21

Para saber se X é um número primo, vc testa se ele é divisivel por todos os números inteiros desde 2 até a raiz quadrada de X - sqrt(X), pois:

Se X não é primo existe um par A,B inteiro tal que A * B = X

onde A >= sqrt(X) e B <= sqrt(X)

Se A e B fossem numeros abaixo de sqrt(X), A * B nunca daria X, o mesmo vale para o caso se forem acima. logo não existe problema em parar o laço de comparação em sqrt(X) :wink:

Este é o algoritmo clássico, existem outros mais parrudos que eu não conheço - mas chegam a gerar GIGASBYTES de numeros primos.

#22

[quote=peczenyj]Para saber se X é um número primo, vc testa se ele é divisivel por todos os números inteiros desde 2 até a raiz quadrada de X - sqrt(X), pois:

Se X não é primo existe um par A,B inteiro tal que A * B = X

onde A >= sqrt(X) e B <= sqrt(X)[/quote]
Só é necessário testar até sqrt(x).

Afinal, se você já achou que esse número é divisível por A, ele já é primo e você não precisar dividir por B.
O último caso é A = sqrt(x) e B = sqrt(x).

#23

meu professor já respondeu essa questão em uma de suas aulas, e eu me lembro que ele fez o seguinte:
no segundo for do programa do inicio do post poderia ser colocado:

for (int j = 2; j < i / 2; j++){
}

ou seja, só seria testado a metade dos numeros anteriores ao numero que esta sendo testado se é primo ou não. Isso diminuiria o loop pela metade, o que deixaria o programa mais rápido.

#24

Então, você pode diminuir mais ainda o loop, se testar até a raíz quadrada.

#25

Apesar de verdadeira a afirmação que você prova que a primalidade de qualquer n testando a primalidade dele com os números de 2 a raiz de n, essa é uma solução totalmente ineficiente para números muito grandes (100 digitos, por exemplo).

#26

Bem no momento estou fazendo um trabalho pra faculdade sobre criptografica e fizemos este exemplo de codigo em java pra definir se um numro eh primo, depois tentaremos implementar o algoritmo de AKS, abaixo o nosso código

 public boolean primo(long num){
        double fat=Math.sqrt(num);
        if((num%2)!=0){
            boolean var=true;
            for(int i=3; i<=fat; i+=2){
                if((num%i)==0){
                    var=false;
                    break;
                }
            }
            return var;
        } else return false;
    }

Esse eh um exemplo de codigo funcinal pra definir a primalidade, mas naum eh eficiente computacionalmete, tente testar ele com um numero de 300 digitos e vc vai entender o porque (olha que chutei baixo).

Se alguem conhecer o funcionamento do algoritmos AKS pra me ajudar no trabalho eu agradeço hehehehe

Outra coisa preciso trabalhar com numeros grandes em java alguem tem uma dica de como trabalhar com numeros assim?

#27

Números grandes?

BigInteger e BigDecimal, ambas do pacote java.math

Falow!

#28

[quote=ZehOliveira]Se reside no fato de que é computacionalmente barato gerar um número muito grande, mas é praticamente impossível (com o anteparo computacional que temos hoje) decompor esse número em seus fatores primos.

Há tanta confiança nesse fato que a criptografia hoje é quase toda ela baseada em números primos. O RSA, por exemplo, se baseia no fato de que é fácil calcular um produto n a partir de dois números primos muito grandes p e q, mas é quase impossível achar p e q fatorando n, já que não há um jeito barato de decompor números enormes

Descobrir a primalidade de um número não faz tanta diferença assim pra criptografia, até existe algoritmo eficiente pra isso, o que realmente importa é achar os fatores de um número.

Vale a pena dá uma pesquisada sobre o assunto, é bastante interessante. Caso se interesse mais em RSA, pode dá uma lida em http://theory.lcs.mit.edu/~rivest/rsapaper.pdf[/quote] Ótimo post.
E quem criar a equação que descubra os primos ainda leva uma grana:
http://itrain.org/itinfo/2002/it020703.html

É de 2002, mas como ninguém descobriu até agora, deve estar valendo

#29

Opa, mais respostas, legal!

Então, eu andei vendo uns outros códigos de cálculo de números primos e achei esse daqui, que foi escrito em Python. Eu achei ele no http://www.pythonbrasil.com.br/moin.cgi/DeterminandoPrimos

No artigo, o autor vai analisando diversos algoritmos e mostrando formas de melhorá-lo. O último (e melhor) é:

**Obs: Isso é Python**
from math import sqrt

print "Primos: 2",

primos, limite = [2,], 100

for numero in xrange(3,limite+1,2): #pula de dois em dois
    ehprimo = 1
    for i in primos:
        if numero % i == 0:
            ehprimo = 0
            break
        if i > sqrt(numero):
            break
    if (ehprimo):
        primos.append(numero)
        print numero,

Esse algoritmo é muito rápido. Não tem nem comparação com o primeiro. Eu fiz umas medições e ele calcula os números primos até 300.000 em 17 segundos. Usando esse algoritmo do meu primeiro post, eu fiz o cálculo de 300.000 em 3 minutos e 3 segundos.

Acho que há muito da questão de linguagem interpretada e linguagem compilada, certo? Eu não sei dizer de que maneira isso afeta, mas eu sei que afeta. Com o que o tiagoboy falou, o código já fica bem mais rápido.[quote]Obs: Isso é Java
for (int j = 2; j < i / 2; j++)[/quote]
Com números primos até 150.000, o python faz em 10 segundos e o java em 25 segundos.

Uma coisa que eu notei é que o código em Python imprime todos os números na mesma velocidade. Já o código em Java começa imprimindo rápido e depois dá uma diminuída na velocidade e meio que mantém um pouco mais lento. Por que será que isso acontece?

Acontece que o algoritmo é diferente e é normal que haja diferença no tempo de execução. Então eu queria saber como ficaria esse algoritmo em Python escrito em Java.

Uma implementação que o autor faz é nessa linha: [quote]for numero in xrange(3,limite+1,2): #pula de dois em dois[/quote] A explicação: [quote]Há uma outra otimização faltando que diminui o número de testes, que é fazer o laço externo contando apenas os números ímpares (ou seja, começando de um número ímpar, contando de dois em dois). [/quote]
E eu gostaria de saber: primeiro, se dá para fazer isso em Java (pular de dois em dois) e a explicação matemática para isso, ou seja, porque só é preciso testar em número ímpares?

Legal que as pessoas tão respondendo ao meu tópico! Achei que seria interessante uma análise coletiva de algum código. Esse algoritmo de números primos é muito legal de estudar!

[]'s,

Tork

#30

Claro que dá pra pular de 2 em 2:

for (int i = 0; i < x; i += 2)

Não é necessário testar com números pares porque se o número é divisível por um par, então ele também é divisível por 2 (que já foi testado lá no começo).
Par * qualquer_coisa = par

Sobre o desempenho, você disse que os algoritmos são diferentes. Testa o mesmo algoritmo nos dois.

#31

[quote=balarini][quote=ZehOliveira]Se reside no fato de que é computacionalmente barato gerar um número muito grande, mas é praticamente impossível (com o anteparo computacional que temos hoje) decompor esse número em seus fatores primos.

Há tanta confiança nesse fato que a criptografia hoje é quase toda ela baseada em números primos. O RSA, por exemplo, se baseia no fato de que é fácil calcular um produto n a partir de dois números primos muito grandes p e q, mas é quase impossível achar p e q fatorando n, já que não há um jeito barato de decompor números enormes

Descobrir a primalidade de um número não faz tanta diferença assim pra criptografia, até existe algoritmo eficiente pra isso, o que realmente importa é achar os fatores de um número.

Vale a pena dá uma pesquisada sobre o assunto, é bastante interessante. Caso se interesse mais em RSA, pode dá uma lida em http://theory.lcs.mit.edu/~rivest/rsapaper.pdf[/quote] Ótimo post.
E quem criar a equação que descubra os primos ainda leva uma grana:
http://itrain.org/itinfo/2002/it020703.html

É de 2002, mas como ninguém descobriu até agora, deve estar valendo[/quote]

ha alguns anos (uns 3) uns caras da india descobriram um algoritmo polinomial para isso… vou tentar achar

[edit]
achei aqui:
http://mathworld.wolfram.com/AKSPrimalityTest.html
[/edit]

#32

[color=red]Como faço para após calcular os números primos ele insira em uma pilha ou fila ou lista linear, pode ser tanto estática quanto dinâmica, e no final imprima a Lista , Pilha ou Fila?[/color]

#33