Resolução de Problema: Números Primos com for

O problema

Dado um número inteiro, verificar se ele é primo.

Antes de escrever qualquer linha de código, precisamos entender bem o problema. Um número primo é um número inteiro maior que 1 que possui exatamente dois divisores: o número 1 e ele mesmo.

7 é primo: só é dividido exatamente por 1 e por 7.
6 não é primo: é dividido por 1, 2, 3 e 6 (quatro divisores).
2 é primo (e é o único primo par).
1 não é primo: tem apenas um divisor (ele mesmo).

Lembrete: o que é "dividir exatamente"? Dizemos que d é divisor de n quando a divisão de n por d não deixa resto. Em C, verificamos isso com o operador de resto: n % d == 0 — a mesma ideia usada no exercício de par ou ímpar (numero % 2 == 0).

Pensando na lógica

Se a definição de primo é "ter exatamente dois divisores", uma forma direta de resolver o problema é: contar quantos divisores o número tem. Para isso, testamos todos os candidatos a divisor, de 1 até o próprio número, um por um:

Ler o número n.
Começar um contador de divisores valendo 0.
Para cada valor i de 1 até n: se n % i == 0, somar 1 ao contador.
Ao final, se o contador for igual a 2, o número é primo; caso contrário, não é.

O passo 3 é uma repetição com início e fim bem definidos (de 1 até n) — situação perfeita para o laço for.

Versão 1 — Verificar se um número é primo

#include <stdio.h>

int main() {
    int n, i;
    int divisores = 0;

    printf("Digite um numero inteiro: ");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        if (n % i == 0) {
            divisores++;
        }
    }

    if (divisores == 2) {
        printf("%d e primo\n", n);
    } else {
        printf("%d nao e primo\n", n);
    }

    return 0;
}

Explicando o código:

int divisores = 0; — o contador precisa começar em zero, pois ainda não encontramos nenhum divisor.
for (i = 1; i <= n; i++) — a variável i assume os valores 1, 2, 3, ..., n. Cada valor é um candidato a divisor.
if (n % i == 0) — testa se i divide n exatamente (resto zero).
divisores++; — quando encontramos um divisor, somamos 1 ao contador (é o mesmo que divisores = divisores + 1;).
O if final fica fora do for: só podemos decidir se o número é primo depois de testar todos os candidatos.

Teste de mesa com n = 7:

i	7 % i	É divisor?	divisores
1	0	sim	1
2	1	não	1
3	1	não	1
4	3	não	1
5	2	não	1
6	1	não	1
7	0	sim	2

Ao final, divisores == 2, portanto 7 é primo.

Teste de mesa com n = 6:

i	6 % i	É divisor?	divisores
1	0	sim	1
2	0	sim	2
3	0	sim	3
4	2	não	3
5	1	não	3
6	0	sim	4

Ao final, divisores == 4, portanto 6 não é primo.

E os casos especiais? Para n = 1, o laço encontra só um divisor, então o programa diz corretamente que 1 não é primo. Para n = 0 ou números negativos, o laço nem executa (a condição i <= n já começa falsa), o contador fica em 0 e o programa também responde "não é primo" — o que está correto, pois primos são sempre maiores que 1.

Desafios:

Teste o programa com 2, 13, 15, 97 e 100. Confira as respostas.
Altere o programa para, além de dizer se é primo, exibir quantos divisores o número tem.
Altere o programa para exibir quais são os divisores do número (dica: um printf dentro do if do laço).

Versão 2 — Todos os primos entre 2 e N

Escreva um programa em C que leia um número inteiro N, maior que 1, e exiba todos os números primos entre 2 e N.

Já sabemos verificar se um número é primo. Agora precisamos fazer essa mesma verificação para cada número de 2 até N. Ou seja: vamos repetir a Versão 1 inteira várias vezes. Isso nos leva a um laço dentro de outro laço (laços aninhados):

O laço externo percorre os números que queremos testar: num vai de 2 até N.
O laço interno é exatamente a lógica da Versão 1: conta os divisores de num.

#include <stdio.h>

int main() {
    int n, num, i;
    int divisores;

    printf("Digite um numero inteiro maior que 1: ");
    scanf("%d", &n);

    printf("Primos entre 2 e %d:\n", n);

    for (num = 2; num <= n; num++) {
        divisores = 0;

        for (i = 1; i <= num; i++) {
            if (num % i == 0) {
                divisores++;
            }
        }

        if (divisores == 2) {
            printf("%d\n", num);
        }
    }

    return 0;
}

Explicando o código:

O trecho das linhas 13 a 23 é a mesma lógica da Versão 1, só que aplicada à variável num em vez de n.
divisores = 0; agora fica dentro do laço externo. Isso é essencial: cada número testado precisa começar a contagem do zero. Se o contador fosse zerado apenas uma vez, antes do laço, os divisores de um número iriam se acumulando com os do número seguinte e o programa daria respostas erradas.
Quando o número é primo, apenas exibimos ele. Os números não primos são simplesmente ignorados (não há else).

Exemplo de execução com N = 20:

Digite um numero inteiro maior que 1: 20
Primos entre 2 e 20:
2
3
5
7
11
13
17
19

Resolver um problema a partir de outro Repare na estratégia: primeiro resolvemos um problema menor (verificar um número) e testamos até ter certeza de que funcionava. Depois, reaproveitamos essa solução dentro de uma repetição para resolver o problema maior. Quebrar um problema em partes menores é uma das habilidades mais importantes da programação.

Desafios:

Mova a linha divisores = 0; para antes do laço externo e rode com N = 20. O que acontece? Por quê?
Altere o programa para exibir os primos na mesma linha, separados por espaço.
Altere o programa para, ao final, mostrar quantos primos foram encontrados entre 2 e N.
Altere o programa para validar a entrada: se o usuário digitar um N menor ou igual a 1, exibir uma mensagem de erro.

Para refletir

A lógica usada aqui é a mais simples possível: testa todos os candidatos a divisor. Ela funciona, mas faz trabalho desnecessário. Pense:

Se já encontramos um divisor além do 1 (por exemplo, o 2 no número 100), ainda precisamos continuar testando?
Um número n pode ter algum divisor maior que n / 2, além dele mesmo?
Como essas observações poderiam deixar o programa mais rápido para números grandes?