n�meros primos

Question

pessoal, preciso fazer um pequeno programa matem�tico que descubra se o n�mero fornecido pelo usu�rio � PRIMO ou n�o...como fa�o isso essa an�lise?...

Rjun · Answer

[code:1:2a549f152c]function Primo(numero: integer): boolean;var  Divisores: integer;  i: integer;begin  result := false;  Divisores := 0;  for i := 1 to numero do    if ((numero mod i) = 0) then      inc(Divisores);  if (numero = 1) or (Divisores = 2) then    result := true;end;[/code:1:2a549f152c]...

Rafael Santana · Answer

amigo, vc poderia explicar esse c�digo?obrigado...

Rjun · Answer

Bom, como voc� deve saber, n�mero primo e todo n�mero natural, maior que 1 que s� tem 2 divisores (o n�mero 1 e o pr�prio numero).

Entao, fiz um loop do numero 1 ate o numero informado. Em cada volta do loop fa�o a divisao do numero pelo indice e vejo se o resto � zero. Se for zero, entao o indice � um divisor do numero.

Incremento a variavel Divisores e ao final da func�o vejo se o n�mero de divisores � igual a 2. Se for, ent�o o numero informado � um numero primo.

A fun��o precisa de uma corre�ao no final. O c�digo

  if (numero = 1) or (Divisores = 2) then 
    result := true;

deve ser trocado por :

  if Divisores = 2 then result := true;

Brunobaco · Answer

[quote:006baf5d03]function Primo(numero: integer): boolean; var   Divisores: integer;   i: integer; begin   result := false;   Divisores := 0;   for i := 1 to numero do     if ((numero mod i) = 0) then       inc(Divisores);   if (numero = 1) or (Divisores = 2) then     result := true; end; [/quote:006baf5d03]Amigo, a variavel numero � o numero passado como parametro. Ent�o entra no la�o for. Qdo se faz um numero mod i, o codigo est� pegando o resto da divis�o apenas, e n�o quociente. Se o resultado for zero (ou seja, divisivel pelo numero), incrementa a vari�vel divisores. ap�s terminar o for, verifica se o numero passado � o numero 1 (o numero 1 � primo, e ele s� ser� dividido por 1,  ou seja, uma unic vez), e se divisores for igual a zero, significa que ele s� foi dividido 2 vezes, uma vez por 1 (todos s�o divis�veis por 1) e por ele mesmo. Isso significa que ele � primo.Explica��o: Um n�mero primo � aquele que � divisivel por 1 e por ele mesmo.Entendeu??Espero ter ajudadoBruno Augusto...

Edilcimar · Answer

voc� n�o precisa checar at� o valor do n�mero e sim at� a raiz quadrada dele, por ex. para saber se 1 milh�o � primo basta checar at� a raiz de 1 milh�o (1 mil), se n�o for primo at� a�, da� para frente n�o ser�

Marco Salles · Answer

[quote:45adb4b030]voc� n�o precisa checar at� o valor do n�mero e sim at� a raiz quadrada dele, por ex. para saber se 1 milh�o � primo basta checar at� a raiz de 1 milh�o (1 mil), se n�o for primo at� a�, da� para frente n�o ser�[/quote:45adb4b030]O Problema � que a Grande muaioria de  N�meros , N�o retornan Raiz Quadrada InteirasPor exemplo ::: 12346787980980901 � Primo ?????Sei la:???e sua raiz quadrada �  3513799.65008 :cry:...

Edilcimar · Answer

se at� o seu n�mero 3513799.65008, desprezadas as casas decimais, ele for primo da� para frente ser�, ent�o basta checar at� 3513799...

Andremuller · Answer

o mais importante � parar no momente em que achou o terceiro divisor

function Primo(numero: integer): boolean;
var
  Divisores: integer;
  i: integer;
begin
  result := false;
  Divisores := 0;

  for i := 1 to numero do
    if ((numero mod i) = 0) then
    begin
      inc(Divisores);
      if Divisores > 2 then
        Break;
    end;
  if (numero = 1) or (Divisores = 2) then
    result := true;

end;

Edilcimar · Answer

no m�mero primo o terceiro divisor ser� ele pr�prio. se utilizar assim e o n�mero for grande vai fazer conta desnecess�ria, fa�a o c�lculo de tempo para verificar se o n�mero 4 bilhoes e 1 � primo e calcule o tempo, depos fa�a da minha maneira e veja o tempo ganho

Marco Salles · Answer

[quote:dc2d1a7553]se at� o seu n�mero 3513799.65008, desprezadas as casas decimais, ele for primo da� para frente ser�, ent�o basta checar at� 3513799[/quote:dc2d1a7553]Sera :?:  :?: Que para analisar o Numero 12346787980980901 a gente analisa o Numero 3513799 :?:  :?:  :?: Bem , o fato � que o assunto � polemico:Ver[quote:dc2d1a7553]The Electronic Frontier Foundation is offering a $100,000 award to the first person or group to discover a ten million digit prime number! fonte: //www.mersenne.org/[/quote:dc2d1a7553]e mesmo outro Post interresante://forum.devmedia.com.br/viewtopic.php?t=41137&highlight=primos&sid=f1a58c8990777a29760a6189af124603...

Rjun · Answer

[quote:a0b8a7184a]voc� n�o precisa checar at� o valor do n�mero e sim at� a raiz quadrada dele, por ex. para saber se 1 milh�o � primo basta checar at� a raiz de 1 milh�o (1 mil), se n�o for primo at� a�, da� para frente n�o ser� [/quote:a0b8a7184a]Bom, seguindo a l�gica para saber se 25 � primo, bastaria chegar at� 5. 5 � primo mas 25 n�o, ja que 25 � divisivel por 1, 5, e 25. Ent�o acho que sua l�gica esta errada. Se algu�m tiver outra sugest�o posta a�....

Edilcimar · Answer

Desculpe o engano na escrita, o certo � se ele n�o for primo at� o n�mero 3513799.65008, desprezadas as casas decimais, da� para frente ele N�O ser�, portanto basta checar at� 3513799. Isto � uma regra matem�tica. O probelma de achar um primo com 10 milh�es de d�gitos � que a ra�z quadrada do mesmo anda ter� mais de 3 mil d�gitos, voc� se habilita a gastar anos para o computador fazer este tipo de conta?

Andremuller · Answer

pois �, s� que 4 bilh�es n�o � primo e fa�a a sua maneira e a minha (que s� completei a id�ia do colega n�o � propriamente minha id�ia), na minha ele j� cai fora nas primeiras itera��es.

O neg�cio ent�o � fazer um mix das duas id�ias.
Se d� pra fazer s� at� a raiz quadrada, o que pode ser porque n�o tenho certeza, melhor, s� que de qualquer forma deve-se parar ao encontrar o terceiro divisor

Massuda · Answer

[quote:9650ab9f8d=�Rjun�]Bom, seguindo a l�gica para saber se 25 � primo, bastaria chegar at� 5. 5 � primo mas 25 n�o, ja que 25 � divisivel por 1, 5, e 25. Ent�o acho que sua l�gica esta errada. Se algu�m tiver outra sugest�o posta a�.[/quote:9650ab9f8d]Pelo que me lembro, a regra � essa mesma que o colega Edilcimar postou... basta testar at� a raiz quadrada do valor testado.Isso parte do princ�pio que todo n�mero natural n�o nulo � divis�vel por 1 e por ele pr�prio; qualquer outro divisor estar� entre 2 e a raiz quadrada do valor testado....

Edilcimar · Answer

� isto a� massuda, a id�ia � esta que voc� disse
para saber se o n�mero 25 � primo basta ir de 1 at� a raiz de 25 (que � 5), se at� a� o n�mero s� for divis�vel por 1 ent�o ele � primo, como 25 � divis�vel por 5 ent�o 25 n�o � primo

F�rum n�meros primos #280027