Ir para conteúdo
Fórum Script Brasil
  • 0

Números Primos


Paulo Nobre

Pergunta

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 para o comentário
Compartilhar em outros sites

18 respostass a esta questão

Posts Recomendados

  • 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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

...

Link para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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 para o comentário
Compartilhar em outros 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

Editado por Paulo Nobre
Link para o comentário
Compartilhar em outros sites

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152k
    • Posts
      651,8k
×
×
  • Criar Novo...