Faça um programa em C se imprima os N 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 números que sejam simultaneamente primos e pertençam à sequência de Fibonacci.
Informações dadas e o que é pedido:
  • Entrada: um inteiro N (assumimos N\ge 1 em geral; se N\le 0 o programa pode não imprimir nada).
  • Saída: os primeiros N números que satisfazem duas propriedades:
    1. São termos da sequência de Fibonacci.
    2. São números primos.
  • Observação: vou usar a definição padrão da sequência de Fibonacci com
F_0 = 0,\quad F_1 = 1,
e para k\ge 2
F_k = F_{k-1} + F_{k-2}.
Com essa definição, os primeiros termos são 0,1,1,2,3,5,8,13,21,\dots. Entre esses, os primos conhecidos mais cedo são 2,3,5,13,89,233,\dots. O programa deve gerar termos de Fibonacci na ordem crescente e imprimir aqueles que são primos, até obter N deles.

Passo 2

Vamos entender as duas coisas que precisamos reconhecer no programa.
  1. Sequência de Fibonacci:
  • A maneira prática de gerar termos de Fibonacci é iterativa: manter duas variáveis (chamei de a e b) com os dois últimos termos e calcular o próximo como f = a + b. Depois desloca-se: a \leftarrow b, b \leftarrow f.
  • Começando em a=0, b=1, as somas sucessivas dão a sequência 1, 2, 3, 5, 8, 13, …
  1. Teste de primalidade (noção e método simples):
  • Um número inteiro n\ge 2 é primo se não tem divisores inteiros d tais que 2 \le d \le n-1.
  • Uma otimização clássica: se n é composto, então existe um divisor d com 2\le d \le \lfloor\sqrt{n}\rfloor. Logo basta testar divisores até \lfloor\sqrt{n}\rfloor.
  • Implementação prática (rápida o bastante para valores de Fibonacci que cabem em 64 bits):
    • Tratar casos pequenos: se n<2 não é primo; se n==2 é primo; se n\%2==0 e n>2 não é primo.
    • Testar divisores ímpares d com 3,5,7,\dots até d \le n/d. Usar a comparação d \le n/d evita calcular uma raiz em ponto flutuante e evita overflow no quadrado.

Passo 3

Por que testar divisores até \sqrt{n} funciona? Explicação didática curta:
  • Se n tem um divisor d com 1<d<n, então existe outro divisor e=n/d.
  • Se ambos fossem maiores que \sqrt{n}, então d\cdot e > \sqrt{n}\cdot\sqrt{n} = n, contradizendo d\cdot e = n.
  • Logo pelo menos um entre d e e é \le \sqrt{n}. Portanto se não existe divisor \le \sqrt{n}, n é primo.

Passo 4

Estratégia do programa (passo-a-passo lógico):
  1. Ler N.
  2. Inicializar contadores e variáveis de Fibonacci: a\leftarrow 0, b\leftarrow 1, contador de primos encontrados c\leftarrow 0.
  3. Enquanto c < N:
    • Verificar se a soma a+b vai causar overflow no tipo inteiro escolhido; se houver risco, interromper (não dá para gerar mais termos).
    • Calcular f = a + b (próximo termo de Fibonacci).
    • Atualizar a \leftarrow b, b \leftarrow f.
    • Testar se f é primo usando o método do Passo 3.
    • Se for primo, imprimir f e incrementar c.
  4. Quando c alcançar N, terminar.
Observações práticas:
  • Usarei o tipo unsigned long long em C para armazenar os termos de Fibonacci (capacidade até 2^{64}-1). Para N muito grande pode ocorrer overflow antes de encontrar N primos; no contexto de prova normalmente N é pequeno o suficiente.
  • Para evitar overflow ao calcular f=a+b, verificar se \texttt{ULLONG\_MAX - b < a} antes de somar.

Passo 5

Pseudocódigo detalhado (nomes entre .. quando são variáveis):
  • Ler N.
  • a \leftarrow 0; b \leftarrow 1; c \leftarrow 0.
  • Enquanto c < N faça:
    • Se \texttt{ULLONG\_MAX} - b < a então pare (overflow).
    • f \leftarrow a + b.
    • a \leftarrow b.
    • b \leftarrow f.
    • Se isPrime( f) então:
      • imprimir f;
      • c \leftarrow c + 1.
  • Fim.
Função isPrime( n):
  • Se n < 2 retorne falso.
  • Se n == 2 retorne verdadeiro.
  • Se n \% 2 == 0 retorne falso.
  • Para d \leftarrow 3 até d \le n/d com passo 2:
    • Se n \% d == 0 retorne falso.
  • 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> (para ULLONG_MAX).
  • Use scanf para ler N e printf para 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 long e usar a comparação d <= n / d para evitar multiplicação que pode causar overflow.
  • Seja cuidadoso com N pequeno: a sequência contém 1 duas vezes no começo; contudo 1 não é primo, então não será impressa.
  • Teste exemplo: para N=6 o programa deve imprimir, em linhas separadas, os valores 2,3,5,13,89,233.

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;
}

Exercícios relacionados