Números primos

Delphi

11/04/2004

Como fazer um programa saber quais são os números primos de 1 até 100?


Bfalcon

Bfalcon

Curtidas 0

Respostas

Aroldo Zanela

Aroldo Zanela

11/04/2004

Colega,

http://delphiforum.icft.com.br/forum/viewtopic.php?t=34607


GOSTEI 0
Beppe

Beppe

11/04/2004

Este é um algoritmo muito simples para verificar todos os números primos de 1 até X, usando uma tabela. Pode ser otimizado de várias maneiras, não o fiz apenas para deixar o código mais conciso.

procedure TForm1.Button1Click(Sender: TObject);
const
  Max = 100;
var
  Primos: array[1..Max] of Boolean;
  I, J: Integer;
begin
  FillChar(Primos, SizeOf(Primos), 1);
  Primos[1] := False;
  for I := 2 to Trunc(Sqrt(Max)) do
  begin
    J := I + I;
    while J <= Max do
    begin
      Primos[J] := False;
      Inc(J, I);
    end;
  end;
...
end;


A idéia é considerar todos os números como sendo primos até que se prove o contrário, exceto o 1, que é sabido não primo. Um laço é usado para eliminar da lista todos os múltiplos(não inclusive) da variável de controle.


GOSTEI 0
Aroldo Zanela

Aroldo Zanela

11/04/2004

Colega,

Pra testar: http://www.utm.edu/research/primes/lists/small/1000.txt


GOSTEI 0
Edilcimar

Edilcimar

11/04/2004

procedure TForm1.Button1Click(Sender: TObject); 
const 
  Max = 100; 
var 
  Primos: array[1..Max] of Boolean; 
  I, J: Integer; 
begin 
  FillChar(Primos, SizeOf(Primos), 1); 
  Primos[1] := False; 
  for I := 2 to Trunc(Sqrt(Max)) do 
  begin 
    J := I + I; 
    while J <= Max do -> AQUI BASTA IR ATÉ MAX/2 - e vc ganha tempo de processamento em números grandes
    begin 
      Primos[J] := False; 
      Inc(J, I); 
    end; 
  end; 
... 
end;



GOSTEI 0
Bfalcon

Bfalcon

11/04/2004

Muito obrigado pessoal.


GOSTEI 0
Nerdex

Nerdex

11/04/2004

Só por curiosidade: até 100 todu bem..., mas se houverem maiores casas decimais a coisa complica... Existe um prêmio milionário para quem descobir um algorítmo que realize esta operação com sucesso para números de grandes proporções...

Quem disse: foi meu antigo professor de Lógica...tá ?!

Abraço


GOSTEI 0
Bfalcon

Bfalcon

11/04/2004

Só por curiosidade: até 100 todu bem..., mas se houverem maiores casas decimais a coisa complica... Existe um prêmio milionário para quem descobir um algorítmo que realize esta operação com sucesso para números de grandes proporções... Quem disse: foi meu antigo professor de Lógica...tá ?! Abraço

É?
Não sabia disso...


GOSTEI 0
Aroldo Zanela

Aroldo Zanela

11/04/2004

Colegas,

Se tem prêmio eu não sei, mas que o pessoal está procurando um maior a cada dia, ah sim, com certeza. Vejam:

http://www.estadao.com.br/tecnologia/internet/2003/dez/17/46.htm


GOSTEI 0
Cebikyn

Cebikyn

11/04/2004

Tem premio sim:

[i:d25d23960a]The Electronic Frontier Foundation is offering a $100,000 award to the first person or group to discover a ten million digit prime number![/i:d25d23960a] fonte: http://www.mersenne.org/



GOSTEI 0
Paulo_amorim

Paulo_amorim

11/04/2004

Só por curiosidade: até 100 todu bem..., mas se houverem maiores casas decimais a coisa complica... Existe um prêmio milionário para quem descobir um algorítmo que realize esta operação com sucesso para números de grandes proporções... Quem disse: foi meu antigo professor de Lógica...tá ?! Abraço


Olá

:idea: Se eu bem me lembro, li na revista Scientific American Brasil de uns 3 meses atrás que um grupo de 4 matematicos indianos (tinha que ser ne) desenvolveram um algoritmo...Lá tinha o site, mas nao anotei.
Vou ver se acho a revista em casa e se achar o site eu posto aqui.

Até+


GOSTEI 0
Beppe

Beppe

11/04/2004

:idea: Se eu bem me lembro, li na revista Scientific American Brasil de uns 3 meses atrás que um grupo de 4 matematicos indianos (tinha que ser ne) desenvolveram um algoritmo...Lá tinha o site, mas nao anotei. Vou ver se acho a revista em casa e se achar o site eu posto aqui. Até+

Eu vi uma vez, mas era dum cara só, ou dois até, o pseudo código do algoritmo ocupava umas 15 linhas só(lógico q implementando ia mais).

Eu já vi buscarem primos de tudo q eh jeito: twins(dois números impares consecutivos), de mersenne(igual a 2 elevado a um número x - 1). Eu já encontrei um site que distribua um programa para q a pessoa em casa ajudasse a procurar tais números


GOSTEI 0
POSTAR