Faça um programa em
se imprima os
primeiros números que sejam primos e façam parte da série de Fibonacci.
Passo 1
O enunciado pede que eu escreva um programa em C que imprima os primeiros
números que sejam simultaneamente primos e pertençam à sequência de Fibonacci.
Informações dadas e o que é pedido:
- Entrada: um inteiro
(assumimos em geral; se o programa pode não imprimir nada). - Saída: os primeiros
números que satisfazem duas propriedades: - São termos da sequência de Fibonacci.
- São números primos.
- Observação: vou usar a definição padrão da sequência de Fibonacci com
e para
Com essa definição, os primeiros termos são
. Entre esses, os primos conhecidos mais cedo são
. O programa deve gerar termos de Fibonacci na ordem crescente e imprimir aqueles que são primos, até obter
deles.
Passo 2
Vamos entender as duas coisas que precisamos reconhecer no programa.
- Sequência de Fibonacci:
- A maneira prática de gerar termos de Fibonacci é iterativa: manter duas variáveis (chamei de
e ) com os dois últimos termos e calcular o próximo como . Depois desloca-se: , . - Começando em
, , as somas sucessivas dão a sequência 1, 2, 3, 5, 8, 13, …
- Teste de primalidade (noção e método simples):
- Um número inteiro
é primo se não tem divisores inteiros tais que . - Uma otimização clássica: se
é composto, então existe um divisor com . Logo basta testar divisores até . - Implementação prática (rápida o bastante para valores de Fibonacci que cabem em 64 bits):
- Tratar casos pequenos: se
não é primo; se é primo; se e não é primo. - Testar divisores ímpares
com até . Usar a comparação evita calcular uma raiz em ponto flutuante e evita overflow no quadrado.
- Tratar casos pequenos: se
Passo 3
Por que testar divisores até
funciona? Explicação didática curta:
- Se
tem um divisor com , então existe outro divisor . - Se ambos fossem maiores que
, então , contradizendo . - Logo pelo menos um entre
e é . Portanto se não existe divisor , é primo.
Passo 4
Estratégia do programa (passo-a-passo lógico):
- Ler
. - Inicializar contadores e variáveis de Fibonacci:
, , contador de primos encontrados . - Enquanto
: - Verificar se a soma
vai causar overflow no tipo inteiro escolhido; se houver risco, interromper (não dá para gerar mais termos). - Calcular
(próximo termo de Fibonacci). - Atualizar
, . - Testar se
é primo usando o método do Passo 3. - Se for primo, imprimir
e incrementar .
- Verificar se a soma
- Quando
alcançar , terminar.
Observações práticas:
- Usarei o tipo
unsigned long longem C para armazenar os termos de Fibonacci (capacidade até). Para N muito grande pode ocorrer overflow antes de encontrar primos; no contexto de prova normalmente é pequeno o suficiente. - Para evitar overflow ao calcular
, verificar se antes de somar.
Passo 5
Pseudocódigo detalhado (nomes entre
quando são variáveis):
- Ler
. -
; ; . - Enquanto
faça: - Se
então pare (overflow). -
. -
. -
. - Se isPrime(
) então: - imprimir
; -
.
- imprimir
- Se
- Fim.
Função isPrime(
):
- Se
retorne falso. - Se
retorne verdadeiro. - Se
retorne falso. - Para
até com passo 2: - Se
retorne falso.
- Se
- Retorne verdadeiro.
Passo 6
Detalhes de implementação em C que você precisa saber e que eu recomendo:
- Cabeçalhos:
<stdio.h>,<stdbool.h>,<limits.h>(paraULLONG_MAX). - Use
scanfpara lere printfpara imprimir cada número primo de Fibonacci em sua própria linha (mais prático para checar). - A função de primalidade deve trabalhar com
unsigned long longe usar a comparaçãod <= n / dpara evitar multiplicação que pode causar overflow. - Seja cuidadoso com
pequeno: a sequência contém duas vezes no começo; contudo não é primo, então não será impressa. - Teste exemplo: para
o programa deve imprimir, em linhas separadas, os valores .
Resposta
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
bool is_prime(unsigned long long n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (unsigned long long d = 3; d <= n / d; d += 2) {
if (n % d == 0) return false;
}
return true;
}
int main(void) {
int N;
if (scanf("%d", &N) != 1) return 0;
if (N <= 0) return 0;
unsigned long long a = 0, b = 1;
int found = 0;
while (found < N) {
if (ULLONG_MAX - b < a) break; /* overflow ao somar a + b */
unsigned long long f = a + b;
a = b;
b = f;
if (is_prime(f)) {
printf("%llu\n", f);
found++;
}
}
return 0;
}