📚 Capítulo do curso: 07 — Laços Determinísticos (for), Laços Aninhados e Complexidade Big-O da Especialização em Sistemas com C. Leia o capítulo antes de começar.

🔍 Miniprojeto C 07 — Analisador de Primos com Laços Aninhados

Um analisador de números primos por divisão de tentativa, usando laços for aninhados.

🔒 Regra de Ouro: até o Capítulo 07, você conhece o laço for, laços aninhados, break/continue e a noção informal de complexidade Big-O. Ainda não existem arrays (isso é Capítulo 10) nem funções além de main (isso é Capítulo 08). Por isso, esta versão do crivo é resolvida só com for aninhado dentro de main, testando divisibilidade número a número — o Crivo de Eratóstenes “de verdade”, com array de marcação e complexidade O(n log log n), você vai construir no Miniprojeto 10.

🎯 Objetivos

• Dominar laços for aninhados: um for externo percorrendo candidatos, um for interno testando divisores.
• Usar continue para pular iterações que não precisam de processamento adicional.
• Usar break para interromper antecipadamente um laço assim que a resposta já é conhecida.
• Comparar, mesmo que informalmente, a complexidade desta abordagem ingênua (O(n·√n)) com a do Crivo de Eratóstenes real (O(n log log n)), que você implementará mais tarde com arrays.

📋 O problema

Construa um analisador de primos (main.c) que testa, um a um, todos os números inteiros de 2 a 50 e imprime os que forem primos.

Para cada candidato, o teste de primalidade é feito por divisão de tentativa: tenta-se dividir o candidato por cada número inteiro entre 2 e a raiz quadrada aproximada do próprio candidato (basta checar divisor * divisor <= candidato). Se algum divisor encontrado divide o candidato exatamente, ele não é primo — nesse instante, o laço interno deve parar imediatamente com break, pois não há motivo para continuar testando. Números pares maiores que 2 podem ser descartados de imediato com continue, sem entrar no laço interno.

graph TD
    A["for candidato = 2 ate 50"] --> B{"candidato == 2?"}
    B -->|Sim| C["imprime 2, continue"]
    B -->|Nao| D{"candidato e par?"}
    D -->|Sim| E["continue (descarta)"]
    D -->|Nao| F["for divisor = 3; divisor*divisor <= candidato; divisor += 2"]
    F --> G{"candidato % divisor == 0?"}
    G -->|Sim| H["primo = false, break"]
    G -->|Nao| F
    H --> I{"primo?"}
    F -->|fim do for| I
    I -->|Sim| J["imprime candidato"]
    I -->|Nao| A
    J --> A
    C --> A
    E --> A

    style F fill:#0284c7,stroke:#38bdf8,color:#ffffff
    style H fill:#dc2626,stroke:#f87171,color:#ffffff
    style J fill:#059669,stroke:#34d399,color:#ffffff

🧰 Ambiente

O mesmo do Miniprojeto 01: gcc 8 ou mais novo. No Windows, rode chcp 65001 se os emojis aparecerem quebrados.

Passo 1 — Compilar o esqueleto

🎯 Objetivo: partir de um código que compila e roda, antes de escrever qualquer linha.

⌨️ Faça: crie a pasta c_mini_07, salve o código abaixo como main.c e rode:

gcc -Wall -Wextra -Wpedantic -std=c17 main.c -o app
./app          # Linux/macOS
.\app.exe      # Windows (PowerShell)

📄 src/esqueleto.c

/*
 * Miniprojeto 07: Analisador de Primos e Crivo de Eratostenes (versao ingenua)
 * Regra: usa for aninhado, break e continue (Capitulo 07). Sem arrays, sem funcoes alem de main.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void) {
    printf("====================================================\n");
    printf(" 🔢 ANALISADOR DE NUMEROS PRIMOS DE 2 A 50\n");
    printf("====================================================\n");
    printf("Primos encontrados: ");

    for (int candidato = 2; candidato <= 50; candidato++) {
        // TODO 1: se candidato == 2, imprima "2 " e use continue
        // (2 e o unico numero primo par, nao precisa testar divisores)

        // TODO 2: se candidato for par (candidato % 2 == 0) e maior que 2,
        // use continue para descartar sem testar nenhum divisor

        bool primo = true;

        // TODO 3: laco for interno "divisor", comecando em 3, com condicao
        // divisor * divisor <= candidato, incrementando de 2 em 2 (so impares)
        // TODO 4: dentro dele, se candidato % divisor == 0, marque
        // primo = false e use break

        if (primo) {
            printf("%d ", candidato);
        }
    }

    printf("\n====================================================\n");

    return EXIT_SUCCESS;
}

✅ Checkpoint: zero avisos do gcc, e a saída é:

🖥️ Saída esperada:

====================================================
 🔢 ANALISADOR DE NUMEROS PRIMOS DE 2 A 50
====================================================
Primos encontrados: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
====================================================

Sem nenhum teste, todo candidato é “primo”: o programa imprime de 2 a 50. Cada passo a seguir vai eliminar uma parte dos números errados.

Passo 2 — Descartar os pares com continue (TODO 1 e 2)

🎯 Objetivo: pular iterações inteiras sem executar o resto do corpo do laço.

⌨️ Faça: no começo do for externo:

1. if (candidato == 2) { printf("%d ", candidato); continue; }, porque 2 é o único primo par;
2. if (candidato % 2 == 0) { continue; }, que descarta todos os outros pares.

✅ Checkpoint: a linha passa a ser 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49. Os pares sumiram, mas ainda há ímpares compostos: 9, 15, 21, 25…

🧯 Se der errado: se o 2 aparece duas vezes, faltou o continue depois de imprimi-lo, e ele também foi impresso pelo if (primo) no fim.

Passo 3 — Testar divisores com for aninhado e break (TODO 3 e 4)

🎯 Objetivo: escrever o laço interno e cortá-lo assim que a resposta for conhecida.

⌨️ Faça: entre bool primo = true; e o if (primo), escreva:

for (int divisor = 3; divisor * divisor <= candidato; divisor += 2) {
    if (candidato % divisor == 0) {
        primo = false;
        break;
    }
}

Acrescente um comentário dizendo que esta abordagem é O(n·√n) e que o Crivo de Eratóstenes de verdade, com array (Miniprojeto 10), é O(n log log n).

✅ Checkpoint: Primos encontrados: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47.

🧯 Se der errado:

• O programa não termina: a condição ou o incremento do for interno ficou vazio. Encerre com Ctrl+C.
• O 9 continua na lista: a condição está divisor * divisor < candidato. Para 9, o divisor 3 precisa ser testado, porque 3 × 3 = 9.

Passo final — Conferir com o gabarito

🎯 Objetivo: validar a saída completa e o código de retorno.

Acrescente, depois da lista, a linha de conclusão com a complexidade, entre linhas de =.

✅ Checkpoint: a saída é esta, e o código de retorno é 0 (echo $? no Linux/macOS ou echo $LASTEXITCODE no PowerShell):

🖥️ Saída esperada:

====================================================
 🔢 ANALISADOR DE NUMEROS PRIMOS DE 2 A 50
====================================================
Primos encontrados: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
====================================================
 ✅ Analise concluida. Complexidade desta versao: O(n * sqrt(n)).
====================================================

Só abra o gabarito depois de chegar até aqui:

/*
 * Miniprojeto 07: Analisador de Primos e Crivo de Eratostenes (versao ingenua)
 * Especializacao em Engenharia de Sistemas em C
 * Regra: usa for aninhado, break e continue (Capitulo 07). Sem arrays, sem funcoes alem de main.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void) {
    printf("====================================================\n");
    printf(" 🔢 ANALISADOR DE NUMEROS PRIMOS DE 2 A 50\n");
    printf("====================================================\n");
    printf("Primos encontrados: ");

    for (int candidato = 2; candidato <= 50; candidato++) {
        if (candidato == 2) {
            printf("%d ", candidato);
            continue; // 2 e o unico primo par; pula o teste de divisores
        }

        if (candidato % 2 == 0) {
            continue; // descarta pares > 2 sem testar nenhum divisor
        }

        bool primo = true;

        // Testa divisores impares de 3 ate a raiz quadrada aproximada do candidato.
        // Complexidade desta abordagem (divisao por tentativa): O(n * sqrt(n)).
        for (int divisor = 3; divisor * divisor <= candidato; divisor += 2) {
            if (candidato % divisor == 0) {
                primo = false;
                break; // achou um divisor exato, nao precisa testar mais nada
            }
        }

        if (primo) {
            printf("%d ", candidato);
        }
    }

    printf("\n====================================================\n");
    // O Crivo de Eratostenes "de verdade" (Miniprojeto 10) marca multiplos
    // num array de booleanos em vez de testar divisibilidade numero a numero,
    // e roda em O(n log log n) -- assintoticamente mais rapido que esta versao.
    printf(" ✅ Analise concluida. Complexidade desta versao: O(n * sqrt(n)).\n");
    printf("====================================================\n");

    return EXIT_SUCCESS;
}

Por que isso importa: cada candidato par acima de 2 é descartado com continue antes mesmo de entrar no laço interno — isso evita trabalho desnecessário. E assim que um divisor exato aparece, o break corta o laço interno na hora, em vez de continuar testando divisores que já sabemos ser irrelevantes. Some esses dois ganhos e ainda assim a abordagem continua sendo O(n·√n): você está evitando trabalho redundante, mas não mudando a estratégia fundamental (testar divisibilidade). O Crivo de Eratóstenes real muda a estratégia — em vez de perguntar “quem divide este número?”, ele marca previamente “estes números são múltiplos de 2, de 3, de 5…”, o que é assintoticamente mais rápido.

🏆 Desafio

Troque o limite superior de 50 para 200 (alterando apenas a condição do for externo) e execute novamente. Depois, no Miniprojeto 10, você vai resolver o mesmo problema com um array de marcação (o Crivo de Eratóstenes de verdade) — compare mentalmente as duas estratégias: aqui você pergunta “quem divide este número?” para cada candidato; lá você vai marcar múltiplos previamente e nunca mais testar divisão. Essa mudança de estratégia é o que separa O(n·√n) de O(n log log n).

✅ Checkpoint: de 2 a 200 existem 46 primos, e o último é 199.

🧭 Navegação

📋 Projetos do curso de C | 📚 Teoria do Capítulo 07 | 🗂️ Hub de projetos