Ir ao conteúdo
  • Cadastre-se
tolki3n

Ajuda com exercício

Recommended Posts

Pessoal, o exercício em questão é 1) determinar se um número é primo e 2) mostrar seus antecessores, incluindo-o na lista.

Dificuldade: Ainda estou no início e muito está sendo cobrado, estou preso no passo 2).

Por enquanto, a codificação está assim:

--------------------------------------------------------------------------

Program Primos;

var i, n: integer;
Primo: boolean; //Variável que destaca apenas 2 valores, é (true) ou não (false) primo!

Begin
writeln ('Informe um número inteiro:');
readln(n);
while (n = 1) do
begin
writeln ('1 não é primo, insira um novo valor: ');
readln (n);
end;

Primo := True; //Iniciando a variável.
i := 2; //Iniciando o contador a partir do primeiro número primo.
while (n > i) do //O laço de repetições deve encerrar em n-1, já que começa em 2 está correto, e também para que não seja dividido por ele mesmo.
begin
if (n mod i) = 0 then //Possibilita verificar se o número é par, 1) números pares não são primos e 2) números com divisores abaixo de si mesmo com resto = 0 também não são primos.
Primo := False; //Verificada as condições, o número não será primo.
i := i + 1; //Contar de um por um.
end;
if Primo then //Não precisa repetir o valor True, pois esta é a regra.
writeln ('O número ',i,' é primo')
else writeln ('O número ',i,' não é primo');
end.

--------------------------------------------------------------------------

Gostaria de saber como mostrar os antecessores do número primo determinado. Agradeço desde já!

Editado por gandalfnho
Use a tag CODE

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá,

Vamos aos pontos:

1) Armazenamento dos números

2) mostrar seus antecessores, incluindo-o na lista

No enunciado não fica claro se será uma faixa de números (de 1 a N) ou se será uma sequência de números digitados pelo usuário e armazenados num array, por exemplo. (usuário digita N números diferentes).

Para cada caso, será uma forma diferente...

a) De 1 a N

Assim, o antecessor será simplesmente o número anterior, ou seja, i-1.

B) Números armazenados num array

Neste caso, o deverá ser o número antecessor da lista, ou seja, "posição do array"-1.

Pelo menos foi assim que eu entendi.

2) Otimização do cálculo de número primo

Por curiosidade...

Existem algumas formas de otimizar mais ainda a verificação. Ex.:

a) Sequência de testes

Com exceção do 2, todo número primo é ímpar. Se é impar, não precisa testar a divisão por números pares... Daí só precisa testar a divisão por números ímpares, ou seja, 3, 5, 7, 9, 11.. (passa a ser i+2). Só isso já reduz mais ou menos pela metade a quantidade de verificações.

Obs.: Na verdade, da verdade, os testes só precisariam ser feitos por números primos. (analise bem... ^_^), mas ai vai dar mais trabalho... só usar números ímpares é mais simples.

B) Maior primeiro divisor

Além de ser sempre ímpar (com exceção do 2), o maior primeiro divisor possível sempre será a raiz do número, ou seja, se existe um número divisor maior que a raiz dele, já haverá outro antes.

Tentando explicar...

Veja, se existe um número "X" divisor de "N" maior que a raiz de "N", e você pegar o quociente "Y" da divisão de "N" por "X", esse "Y" terá que ser menor que "X".

Todo quociente de um número "N" resultado da divisão por um dos seus divisores, também será um divisor. Se esses números (os divisores) forem diferentes, quanto maior um for, o outro terá que ser menor e vice-versa para compensar. A medida que a diferença entre eles diminui, advinha onde chega? Na raiz de "N". Ora! Se um número é menor que a raiz de "N", o outro terá que ser obrigatoriamente maior (para compensar...). No caso, se ele é maior que a raiz de "N", logo significa que existe um outro menor que a raiz "N"... Então nunca o primeiro divisor vai ser maior que a raiz "N", pois terá que existir um outro menor que a raiz "N" para ser multiplicado

Resumindo

Só precisa testar por 2 e o restante ímpar; e basta calcular no máximo até a raiz quadrada de N. "enquanto i menor igual a raiz de n"...

Abraços

Compartilhar este post


Link para o post
Compartilhar em outros sites
Olá,

Vamos aos pontos:

1) Armazenamento dos números

No enunciado não fica claro se será uma faixa de números (de 1 a N) ou se será uma sequência de números digitados pelo usuário e armazenados num array, por exemplo. (usuário digita N números diferentes).

Para cada caso, será uma forma diferente...

a) De 1 a N

Assim, o antecessor será simplesmente o número anterior, ou seja, i-1.

B) Números armazenados num array

Neste caso, o deverá ser o número antecessor da lista, ou seja, "posição do array"-1.

Pelo menos foi assim que eu entendi.

2) Otimização do cálculo de número primo

Por curiosidade...

Existem algumas formas de otimizar mais ainda a verificação. Ex.:

a) Sequência de testes

Com exceção do 2, todo número primo é ímpar. Se é impar, não precisa testar a divisão por números pares... Daí só precisa testar a divisão por números ímpares, ou seja, 3, 5, 7, 9, 11.. (passa a ser i+2). Só isso já reduz mais ou menos pela metade a quantidade de verificações.

Obs.: Na verdade, da verdade, os testes só precisariam ser feitos por números primos. (analise bem... ^_^), mas ai vai dar mais trabalho... só usar números ímpares é mais simples.

B) Maior primeiro divisor

Além de ser sempre ímpar (com exceção do 2), o maior primeiro divisor possível sempre será a raiz do número, ou seja, se existe um número divisor maior que a raiz dele, já haverá outro antes.

Tentando explicar...

Veja, se existe um número "X" divisor de "N" maior que a raiz de "N", e você pegar o quociente "Y" da divisão de "N" por "X", esse "Y" terá que ser menor que "X".

Todo quociente de um número "N" resultado da divisão por um dos seus divisores, também será um divisor. Se esses números (os divisores) forem diferentes, quanto maior um for, o outro terá que ser menor e vice-versa para compensar. A medida que a diferença entre eles diminui, advinha onde chega? Na raiz de "N". Ora! Se um número é menor que a raiz de "N", o outro terá que ser obrigatoriamente maior (para compensar...). No caso, se ele é maior que a raiz de "N", logo significa que existe um outro menor que a raiz "N"... Então nunca o primeiro divisor vai ser maior que a raiz "N", pois terá que existir um outro menor que a raiz "N" para ser multiplicado

Resumindo

Só precisa testar por 2 e o restante ímpar; e basta calcular no máximo até a raiz quadrada de N. "enquanto i menor igual a raiz de n"...

Abraços

Amigo Estilingue, muito obrigado pela ajuda, o exercício pede os números primos de 1 a N, vou anotar suas dicas e tentar aplicá-las, logo volto com os resultados. Estou achando estes exercícios um pouco avançado para a turma, pois ainda estamos em contato inicial com Pascal, por exemplo, não chegamos nas lições de vetores até agora. No momento, estamos estudando contadores e acumuladores, passamos por while, if, for, repeat e outras estruturas mais simples. Mas antes difícil do que fácil, aprende mais. Agradeço pela disposição em ajudar! Volto em breve!

Edit: Consegui fazer na maneira sugerida, com o Crivo de Eratóstenes, certo?

Encontrei várias dicas e exemplos aqui mesmo pelo fórum, mas agora não consigo inserir o algoritmo para acusar quando o número não é primo.

Por exemplo, se inserir 10, ele mostra os primos anteriores ao 10, mas o certo seria dizer: 10 não é primo.

Deve ser mostrado apenas os números primos de 2 até N (se o número inserido for primo). Outra questão que gostaria de maior esclarecimento é em relação ao contador. Não entendi direito como a variável "Divisores" se comporta, pode me esclarecer melhor essa questão?

Obs: Meus algoritmos estão todos comentados, pois o professor só aceita dessa maneira, para certificar que estamos entendendo (e não copiando por aí). Não tenho certeza se os comentários estão corretos!

Código:

----------------------------------------------------------------------

Program Primos;

//Exercício utilizando o método Crivo de Eratóstenes
//Para saber mais visite: [url]http://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes[/url]

var N, i, k, Divisores: integer;

Begin
writeln ('Informe N');
readln (N);

for i:=2 to N do //números primos até N.
begin
Divisores:=2; //Encontrar pelo menos 2 repetições da instrução desejada. Obs: Todo número tem pelo menos 2 divisores.
for k:=2 to trunc(sqrt(i)) do //Crivo de Eratóstenes: dividir apenas até a raíz dos números no intervalo i:=2 até N.
if i mod k = 0 then //Se i=101 por ex., só será dividido até 10, que é sua raíz mais próxima.
begin
Divisores:= Divisores + 1; //Contar de um em um. Obs: Se encontrar mais de 2 divisores não é mais primo.
end;
if Divisores = 2 then //Confirma a operação e imprime os resultados.
write (i:4);
end;
End.

----------------------------------------------------------------------

Editado por gandalfnho
União de posts/use a tag CODE

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×