Jump to content
Fórum Script Brasil
  • 0

Números Primos


Paulo Nobre
 Share

Question

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.

Link to comment
Share on other sites

18 answers to this question

Recommended Posts

  • 0
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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0
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

...

Link to comment
Share on other sites

  • 0

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!!

Link to comment
Share on other sites

  • 0
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;

Link to comment
Share on other sites

  • 0

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!!

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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 by Paulo Nobre
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share



  • Forum Statistics

    • Total Topics
      151k
    • Total Posts
      649.1k
×
×
  • Create New...