Algoritmos numéricos

Divisores e primos

Divisões por tentativa

Um inteiro $n \geq 2$ é primo se seus únicos divisores positivos são 1 e $n$; se tem outro, é composto; 0 e 1 não são nem uma coisa nem outra. A definição sugere de imediato um algoritmo: testar cada candidato $d$ entre 2 e $n - 1$ e declarar o número composto assim que um deles o divida. É o laço do menor divisor da aula Laços, e está correto. Ora, para um primo de dez algarismos ele faz quase dez bilhões de divisões, e quase todas são inúteis, pela razão seguinte.

Segue-se que o número de divisões cai de cerca de $n$ para cerca de $\sqrt{n}$: para $n$ próximo de dois bilhões, de dois bilhões para quarenta e seis mil. O programa usa o padrão da flag da aula Projetar laços corretos: isPrime começa verdadeira e o laço a desliga se encontra um divisor.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} é primo", n);    } else {        std::println("{} não é primo", n);    }}

2147483647

2147483647 é primo

Três decisões merecem comentário. A flag é inicializada com n >= 2, de modo que 0, 1 e os negativos são declarados não primos sem entrar no laço: esquecer esse caso é o erro típico, porque com $n = 1$ o laço não faz nenhuma iteração e o programa declararia primo o 1. A condição do for tem duas partes: a flag, que detém o laço no primeiro divisor, e o limite. E o limite está escrito d <= n / d, que, para inteiros positivos, equivale a $d^2 \leq n$ (a divisão inteira trunca, mas $d$ não supera o quociente truncado exatamente quando não supera $n/d$, porque $d$ é inteiro). O número da entrada, $2^{31} - 1$, é o maior int e é primo; o programa o decide com $46\,339$ restos, os dos candidatos de 2 a $46\,340$.

O invariante do laço é: nenhum inteiro de 2 a $d - 1$ divide $n$, enquanto a flag continuar verdadeira. Vale ao entrar, quando o intervalo de 2 a 1 está vazio; conserva-se, porque, se $d$ não divide $n$, o intervalo cresce com um número que não o divide; e, ao sair com a flag verdadeira, o invariante e a condição falsa, $d^2 > n$, dizem juntos que nenhum candidato até $\sqrt{n}$ divide $n$, que é o que a proposição exige. A variante é a quantidade de candidatos que faltam testar, isto é, de inteiros entre $d$ e $\sqrt{n}$: decresce em um por iteração e não fica abaixo de zero.

A condição que estoura

A maneira natural de escrever o limite é d * d <= n, e é um erro. Com a entrada anterior, o laço chega a $d = 46\,341$, e então o produto $46\,341^2 = 2\,147\,488\,281$ supera o máximo de int.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Primo? {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

O detector de comportamento indefinido detém o programa no produto. Sem ele, o estouro com sinal é comportamento indefinido, e o padrão não diz o que acontece. O que se observa com o GCC no Linux, com e sem otimização, é instrutivo: o produto dá a volta e resulta negativo ou menor que $n$, e como nenhum int supera o máximo, a condição d * d <= n nunca mais deixa de se cumprir; o laço continua testando candidatos durante cerca de dois bilhões de iterações, até chegar a $d = n$, que divide $n$, e o programa declara composto um número primo. Um erro de estouro não se manifesta como um estouro, mas como uma resposta falsa. A forma d <= n / d não pode estourar, porque divide em vez de multiplicar; a aula Bits e biblioteca matemática oferecia outra saída, calcular o limite uma vez com std::sqrt, mas então a exatidão do limite depende do arredondamento do ponto flutuante, e a divisão inteira não tem esse problema.

A aula “Números primos e o teorema fundamental da aritmética”, do curso Álgebra e Geometria I, demonstra que todo inteiro maior que 1 é produto de primos de uma única maneira; as divisões por tentativa são a maneira mais direta de encontrar esse produto, dividindo $n$ por cada divisor encontrado e continuando com o quociente.