Números Primos

[Paulo Nobre]

Os códigos para verificação de que se um número é primo, normalmente usam laços "for" e por isso

trabalham com números inteiros na variação. Acontece que existe uma limitação para a variável

inteira. Como contorno isto se desejo verificar se um número maior do que três bilhões é primo?

Por exemplo a função abaixo verifica se um número n é primo ou não.

function SeraQueSouPrimo(N: Integer): Boolean;
var
  Testando: Integer;
begin
  SeraQueSouPrimo := True;
  for Testando := 2 to N - 1 do
    if (N mod Testando) = 0 then
    begin
      SeraQueSouPrimo := False;
      break; {jump out of the for loop}
    end;
end;

Não é necessário que alguém diga que esta não é a função mais rápida.(Uso outra na prática)

Sei disso!!,apenas coloquei esta como exemplo para fixar a imagem do for variando de 2 até n-1

Como resolveria este problema?

Os matemáticos que trabalham com teoria dos números devem usar algum código para trabalhar com números extremamante grandes, mas não tenho idéia de qual seria.

[Thales Pontes Martins]

Como contorno isto se desejo verificar se um número maior do que três bilhões é primo?

Usando o tipo Int 64 você verifica números até 9.223.372.036.854.775.807(se você for verificar um número desses eu nem sei quanto tempo pode demorar. Alguns séculos?). Entretanto é possível escrever algorítmos para trabalhar com qualquer número, é só você verificar overflow na variável e alocar a variável no tamanho necessário para comportar o número. Calculadoras avançadas usam esse método. Com números reais também é possível, apenas complica um pouco por se tratarem de números decimais com ponto flutuante. Dessa maneira obtem-se números com qualquer precisão.

Não é necessário que alguém diga que esta não é a função mais rápida.(Uso outra na prática)

Sei disso!!,apenas coloquei esta como exemplo para fixar a imagem do for variando de 2 até n-1

Qual é o outro algorítmo que você utiliza que é mais rápido do que esse?

E se você souber um pra calcular o valor de PI também estou interessado. O que eu fiz aqui demorou 1 dia pra calcular 8 casas decimais. Putz. Sei que devem existir algorítmos mais rápidos porque já se calcularam algumas centenas de milhares de dígitos se não me engano.

[Paulo Nobre]

Usando o tipo Int 64 você verifica números até 9.223.372.036.854.775.807

Colocando Int64 dá erro dizendo que: For Loop control must have ordinal type

se você for verificar um número desses eu nem sei quanto tempo pode demorar. Alguns séculos?

De fato quando coloco um número acima de um milhão aqui começa, a demorar bastante.

Imagino que se colocar para rodar num pentium 100 vá demorar um século.

Se não se colocar um Application.ProcessMesages, alguém pode ficar muito nervoso e fazer grandes elogios a progenitora do cara que fez o programa.

...é só você verificar overflow na variável e alocar a variável no tamanho necessário para comportar o número.

Não entendi!!

Qual é o outro algorítmo que você utiliza que é mais rápido do que esse?

Quando escrevi um programinha, a algum tempo atrás e postei uma dúvida alguém me disse

que a função acima era mais lenta e sugeriu fazer o teste da seguinte maneira:

For i:= 2 to Ceil(SQRT(n))do

Na realidade verificando de 2 até n-2 estava perdendo mais tempo. Eu idiotamente nunca tinha parado para

pensar nisto, afinal se p for divisor de n e n = a.p, sendo p e a inteiros com p < a então p^2 < a.p = n.

Assim , para verificar se n é primo ou não , bastava examinar a divisibilidade de n pelos primos menores do que ou iguais a raiz quadrada de n.

Na época nunca tinha ouvido falar desta função Ceil da unit MATH.

Na matemática a gente chama de função máximo inteiro (máximo inteiro de x --->[x]).

E se você souber um pra calcular o valor de PI também estou interessado. O que eu fiz aqui demorou 1 dia pra calcular 8 casas decimais.

Nunca tinha parado para pensar sobre o cálculo de PI, também nunca vi nenhum algoritmo.

Será que você reviveu Arquimedes, que imaginou uma circunferência como o caso limite de um polígono, ou seja com um número de lados n, tendendo ao infinito.

Sei que devem existir algorítmos mais rápidos porque já se calcularam algumas centenas de milhares de dígitos se não me engano.

A alguns anos atrás, li numa revista que o recorde de obtenção de casas decimais para o PI tinha sido

alcançado por um japonês com a ajuda de vários supercomputadores. O cara chegou a obter PI com BILHÕES DE CASAS DECIMAIS. :o

Para brincar com meus alunos decorei o PI como 3,1415926535897932... e digo para eles, só para eles ficarem impressionados, que a cada ano decoro mais duas decimais(maior mentira!! - não passo disto). :P

[Guest Visitante]

Outra dica é verificar se o número é par e depois utilizar o contador começando em três e indo de 2 em 2, já que qualquer número divisivel por numero par também é divisivel por 2. Assim você já diminui pela metade as verificações.

for i=3 to Ceil(Sqrt(n)) Step 2 Do

...

[Paulo Nobre]

Outra dica é verificar se o número é par e depois utilizar o contador começando em três e indo de 2 em 2, já que qualquer número divisivel por numero par também é divisivel por 2. Assim você já diminui pela metade as verificações.

for i=3 to Ceil(Sqrt(n)) Step 2 Do

Bem pensado visitante!!

[Micheus]

Colocando Int64 dá erro dizendo que: For Loop control must have ordinal type

Paulo, acho que teria que trocar o for por while, por exemplo:

function SeraQueSouPrimo(N: Int64): Boolean;
var
  Testando: Int64;
begin
  SeraQueSouPrimo := True;
  Testando := 2;  // com a dica do visitante: Testando := 3;
  while Testando <= (N -1) do
  begin
    if (N mod Testando) = 0 then
    begin
      SeraQueSouPrimo := False;
      break; {jump out of the for loop}
    end;
    Testando := Testando +1;  // com a dica do visitante: Testando := Testando +2; 
  end;
end;

[Paulo Nobre]

Micheus,

funcionou no teste que fiz aqui!

Na fronteira do limite superior encontrei algo estranho 9 seguido de 18 zeros ele aceita.

Nove seguido de 19 zeros não deveria aceitar, mas aceita dizendo que é um número primo, o que não é verdade.

Tentei colocar

While Testando <= Ceil(SQRT(N)) do

no lugar de

While Testando <= N - 1 do

para otimizar o código, mas dá erro de invalid floating pointer operation.

Deve ser por conta do retorno da função Ceil, que é int e não int64, não é isso?

Se existisse uma IntToInt64 daria para contornar!!

[Paulo Nobre]

Alguém sabe como poderia usar a função acima usando int64 e Ceil(SQRT(N)) ?

[s3c]

Alguém sabe como poderia usar a função acima usando int64 e Ceil(SQRT(N)) ?

Não seria: Trunc(SQRT(N)) + 1; ?

[Paulo Nobre]

Não seria: Trunc(SQRT(N)) + 1; ?

Naõ funcionou. Dá a seguinte mensagem de erro:[Error] Unit1.pas(69): Incompatible types apontando para:

While Testando <= Trunc(SQRT(N))+1 do

Não entendo, não deveria dar erro, pois Testando é do tipo int64, sqrt pega um extended e transforma em extende e trunc pega um extended e transforma num int64

[mbleonardo]

O visitante sou eu :) foi meu 1º post neste fórum. Não sei nada de Delphi, mas posso ajudar bastante na lógica.

Obs: Desculpe pelo post inútil

[Thales Pontes Martins]

faça o seguinte ->

function primo(n : int64) : boolean;
var
  r : Extended;
  test, i : int64;
begin
//calcule a raiz quadrada do número ->
  r:=n;
  r:=sqrt(r)+1;
  test:=trunc(r);
  i:=3;
  while (i <= test) do 
  begin
    if ((n mod i) = 0) then
    begin
      result:=false;
      exit;
    end;
    inc(i,2);
  end;
  result:=true;
end;

Acho que é isto. Dessa forma evita-se que seja tirada a raiz a cada loop while e fazendo cair a performance do algorítmo.

[Paulo Nobre]

Funcionou, Thales.

[Thales Pontes Martins]

você reparou que essa função está errada, não é? rsrsrsrsrsrs.

[Paulo Nobre]

Tinha reparado que estava sem o end; final

Testei ela com vários valores e funcionou.

Onde está o erro?

[Thales Pontes Martins]

se for número par ele vai dizer que é primo, tem que colocar antes ->

if ((n mod 2) = 0) then begin result:=false; exit; end;

Certo?

[Paulo Nobre]

É, realmente todos os números que havia testado eram ímpares, afinal o único número primo par (natural) é o dois.

[Thales Pontes Martins]

Mas ainda continua errado porque se for 2 ele vai dizer que não é primo então->

if (((n mod 2) = 0) and (n <> 2)) then begin result:=false; exit; end;

A propósito, conseguí resolver aquele erro do CaptionButton. Acho que agora sai.

[Paulo Nobre]

Mas ainda continua errado porque se for 2 ele vai dizer que não é primo então->

CODEif (((n mod 2) = 0) and (n <> 2)) then begin result:=false; exit; end;

Acho que acrescentando...

if n = 1 then
    begin
      result:= False;
      exit;
    end;
  if n = 2 then
    begin
      result:= False;
      Exit;
    end;
  if ((n mod 2) = 0) then
    begin
      result:=false;
      exit;
    end;

...Resolve definitivamente,não podemos esquecer que 1 não é primo.

A propósito, conseguí resolver aquele erro do CaptionButton. Acho que agora sai.

:D :D :D :D

Edited November 29, 2006 by Paulo Nobre