números primos
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?
Rafael Santana
Curtidas 0
Respostas
Rjun
04/05/2005
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;
GOSTEI 0
Rafael Santana
04/05/2005
amigo, vc poderia explicar esse código?
obrigado
obrigado
GOSTEI 0
Rjun
04/05/2005
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
deve ser trocado por :
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;
GOSTEI 0
Brunobaco
04/05/2005
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;
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 ajudado
Bruno Augusto
GOSTEI 0
Edilcimar
04/05/2005
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á
GOSTEI 0
Marco Salles
04/05/2005
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á
O Problema é que a Grande muaioria de Números , Não retornan Raiz Quadrada Inteiras
Por exemplo ::: 12346787980980901 é Primo ?????
Sei la:???
e sua raiz quadrada é 3513799.65008 :cry:
GOSTEI 0
Edilcimar
04/05/2005
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
GOSTEI 0
Andremuller
04/05/2005
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; GOSTEI 0
Edilcimar
04/05/2005
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
GOSTEI 0
Marco Salles
04/05/2005
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
Sera :?: :?:
Que para analisar o Numero 12346787980980901 a gente analisa o Numero 3513799 :?: :?: :?:
Bem , o fato é que o assunto é polemico:
Ver
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: http://www.mersenne.org/
e mesmo outro Post interresante:
http://forum.devmedia.com.br/viewtopic.php?t=41137&highlight=primos&sid=f1a58c8990777a29760a6189af124603
GOSTEI 0
Rjun
04/05/2005
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á
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í.
GOSTEI 0
Edilcimar
04/05/2005
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?
GOSTEI 0
Andremuller
04/05/2005
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
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
GOSTEI 0
Massuda
04/05/2005
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í.
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.
GOSTEI 0
Edilcimar
04/05/2005
é 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
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
GOSTEI 0
Rjun
04/05/2005
Andre
Acho que sua ideia é a melhor. Apenas necessita fazer um ajuste na função, ja que 1 não é primo.
Acho que sua ideia é a melhor. Apenas necessita fazer um ajuste na função, ja que 1 não é primo.
GOSTEI 0
Edilcimar
04/05/2005
bom a minha funciona, quanto a 1 ser ou não primo existem duas facções, uma dizendo que ele é primo e outra dizendo que não é, mas não cabe aqui este tipo de discussão, pois ficaríamos a vida inteira um tentando convencer o outro, e o que importa é agilizar a conta
GOSTEI 0
Andremuller
04/05/2005
Colegas, reunindo a idéia do edilcimar e a minha, que se preocupam com o tempo de resposta, temos até agora a seguinte função:
function Primo(ANumero: integer): boolean;
var
i, iNumero: integer;
rNumero: Real;
begin
Result := True;
rNumero := Int(Sqrt(ANumero));
iNumero := StrToInt(FloatToStr(rNumero));
for i := 2 to iNumero do
if (ANumero mod i) = 0 then
begin
Result := False;
Exit;
end;
end;GOSTEI 0
Edilcimar
04/05/2005
é exatamente isto
GOSTEI 0
Edilcimar
04/05/2005
está aqui um pedaço do que utilizo para calcular números primos para criptografia rsa
Quantidade1 := StrToInt(Edit1.Text);
While I <= Quantidade1 do
Begin
Cont := 0;
J := 1;
While J <= Round(Sqrt(I)) do
Begin
Resto := I mod J;
If Resto = 0 then
Cont := Cont + 1;
If Cont > 1 then
Break;
J := J + 1;
End;
End;
Quantidade1 := StrToInt(Edit1.Text);
While I <= Quantidade1 do
Begin
Cont := 0;
J := 1;
While J <= Round(Sqrt(I)) do
Begin
Resto := I mod J;
If Resto = 0 then
Cont := Cont + 1;
If Cont > 1 then
Break;
J := J + 1;
End;
End;
GOSTEI 0
Tnaires
04/05/2005
Olá
E não se esqueçam também do Crivo de Eratóstenes... Tendo em mãos um número p, vc pode determinar todos os números primos contidos no intervalo [1, p]. Basta eliminar todos os números do intervalo que são divisíveis por todos os números primos contidos entre 1 e a raiz quadrada d ´p´ (sim, o edilcimar está certo, para decepção de alguns :D). Esse pré-processamento é útil qdo vc precisa determinar várias vezes se um número dentro d um dado intervalo é primo.
Exemplo: entre 1 e 25, vc eliminaria:
- os números divisíveis por 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
- os números divisíveis por 3: 9, 15, 21
- os números divisíveis por 5: 25
- de 7 pra cima não precisa, pq já passou d 5 (raiz d 25)
- o resultado: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23
Abraços
E não se esqueçam também do Crivo de Eratóstenes... Tendo em mãos um número p, vc pode determinar todos os números primos contidos no intervalo [1, p]. Basta eliminar todos os números do intervalo que são divisíveis por todos os números primos contidos entre 1 e a raiz quadrada d ´p´ (sim, o edilcimar está certo, para decepção de alguns :D). Esse pré-processamento é útil qdo vc precisa determinar várias vezes se um número dentro d um dado intervalo é primo.
Exemplo: entre 1 e 25, vc eliminaria:
- os números divisíveis por 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
- os números divisíveis por 3: 9, 15, 21
- os números divisíveis por 5: 25
- de 7 pra cima não precisa, pq já passou d 5 (raiz d 25)
- o resultado: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23
Abraços
GOSTEI 0
Marco Salles
04/05/2005
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
.Agora sim :lol: ..A Ideia não é checar o Numero reultado da raiz , mas fazer a divisão do Numero com todos os numeros ate o Valor da sua Raiz.
Faz sentido e ganha um tempão no processamento :P :P :P
GOSTEI 0
Beppe
04/05/2005
O ´problema´ já está resolvido, certo? (se houver um fator(divisor) entre 2 e Trunc(Sqrt(N)), não é primo)
Quanto a questão do 1 ser ou não primo, a resposta é ´nem primo nem composto´, já que obedece nenhuma das duas leis.
http://en.wikipedia.org/wiki/Prime_numbers
http://www.andrews.edu/~calkins/math/webtexts/numb03.htm
http://primes.utm.edu/largest.html
http://www.math.utah.edu/~alfeld/math/prime.html
http://mathforum.org/library/drmath/view/57058.html
http://www.aaamath.com/B/fra63ax2.htm
http://www.oswego.org/mtestprep/math8/a/primecompositel.cfm
http://mathworld.wolfram.com/PrimeNumber.html
http://mathforum.org/dr.math/faq/faq.prime.num.html
Quanto a questão do 1 ser ou não primo, a resposta é ´nem primo nem composto´, já que obedece nenhuma das duas leis.
http://en.wikipedia.org/wiki/Prime_numbers
http://www.andrews.edu/~calkins/math/webtexts/numb03.htm
http://primes.utm.edu/largest.html
http://www.math.utah.edu/~alfeld/math/prime.html
http://mathforum.org/library/drmath/view/57058.html
http://www.aaamath.com/B/fra63ax2.htm
http://www.oswego.org/mtestprep/math8/a/primecompositel.cfm
http://mathworld.wolfram.com/PrimeNumber.html
http://mathforum.org/dr.math/faq/faq.prime.num.html
GOSTEI 0
Marco Salles
04/05/2005
citacão de tnaires
Não entendi esta colocação... Não sei se o nobre colega esta se referindo a Mim ou ao Rjun
citação de Rjun:
Como so posso falar em meu nome , quero deixar entendido , que em momento nenhum disse o contrário (Nunca disse que o edicilmar estivesse errado, apenas queria entender a sua Sugestão). E tb nunca sinto decpção , por aprender algo novo, muito pelo contário, me sinto é feliz.
sim, o edilcimar está certo, para decepção de alguns
Não entendi esta colocação... Não sei se o nobre colega esta se referindo a Mim ou ao Rjun
citação de Rjun:
Então acho que sua lógica esta errada. Se alguém tiver outra sugestão posta aí.
Como so posso falar em meu nome , quero deixar entendido , que em momento nenhum disse o contrário (Nunca disse que o edicilmar estivesse errado, apenas queria entender a sua Sugestão). E tb nunca sinto decpção , por aprender algo novo, muito pelo contário, me sinto é feliz.
GOSTEI 0
Edilcimar
04/05/2005
para o beppe de um dos links mencionados http://mathforum.org/dr.math/faq/faq.prime.num.html
A prime number [u:048429930a]is a positive integer that has exactly two positive integer factors, 1 and itself[/u:048429930a]. For example, if we list the factors of 28, we have 1, 2, 4, 7, 14, and 28. That´s six factors. If we list the factors of 29, we only have 1 and 29. That´s 2. So we say that 29 is a prime number, but 28 isn´t.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc.
Como eu disse existem 2 facções uma que diz que 1 é primo e outra que diz que ele não é primo. A pessoa acima disse o o primo é o número positivo divisível por 1 e por si próprio, ora 1 é divisível por 1 e por si próprio, mas abaixo ele excluiu o 1, o como eu disse anteriormente isto é o tipo de discussão do ovo e a galinha
A prime number [u:048429930a]is a positive integer that has exactly two positive integer factors, 1 and itself[/u:048429930a]. For example, if we list the factors of 28, we have 1, 2, 4, 7, 14, and 28. That´s six factors. If we list the factors of 29, we only have 1 and 29. That´s 2. So we say that 29 is a prime number, but 28 isn´t.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc.
Como eu disse existem 2 facções uma que diz que 1 é primo e outra que diz que ele não é primo. A pessoa acima disse o o primo é o número positivo divisível por 1 e por si próprio, ora 1 é divisível por 1 e por si próprio, mas abaixo ele excluiu o 1, o como eu disse anteriormente isto é o tipo de discussão do ovo e a galinha
GOSTEI 0
Tnaires
04/05/2005
[quote:5cb7d9fb5d=´Marco Salles´]E tb nunca sinto decpção , por aprender algo novo, muito pelo contário, me sinto é feliz.[/quote:5cb7d9fb5d]
Situação esclarecida :)
Abraços, amigo
Situação esclarecida :)
Abraços, amigo
GOSTEI 0
Beppe
04/05/2005
Eu também postei estes dois links que explicitam que 1 não é primo. Enquanto 1 é divisível por 1 e por ele mesmo, para ser primo precisa ter exatamente 2 divisores (diferentes).
Pode ver também que o 1 nunca é incluído em listagens de números primos nem em fatorações. O ´1´ é então chamado de unidade
http://mathforum.org/library/drmath/view/57058.html
http://mathworld.wolfram.com/PrimeNumber.html
O [url=http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html]teorema fundamental da aritmética[/url] e a [url=http://mathworld.wolfram.com/UniqueFactorization.html]fatorização única[/url] fornecem contra-exemplos.
Pode ver também que o 1 nunca é incluído em listagens de números primos nem em fatorações. O ´1´ é então chamado de unidade
http://mathforum.org/library/drmath/view/57058.html
http://mathworld.wolfram.com/PrimeNumber.html
O [url=http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html]teorema fundamental da aritmética[/url] e a [url=http://mathworld.wolfram.com/UniqueFactorization.html]fatorização única[/url] fornecem contra-exemplos.
GOSTEI 0