Otimizando o algoritmo passo a passo

Acompanhando as lives da bug_elseif, no meia das listas de exercícios que ela estava fazendo tem um exercício pedindo para verificar se um número informado pelo usuário é primo ou não. No chat, muitos faziam sugestões para que o primeiro código feito já fosse o mais otimizado possível, e isso é interessante quando já se sabe a solução do problema. Porém quando não se sabe essa solução, seria possível chegar nela também? É possível otimizar o código pouco a pouco?

Primeira solução

A solução mais simples possível é fazer um algoritmo que leia um número, e verifique se ele é divisível apenas por 1 e por ele mesmo (condição para um número ser primo). Para verificar se um número é divisível por outro, basta verificar o resto da divisão, se o resto da divisão for 0, significa que o primeiro número é divisível pelo segundo, se for diferente de 0, o primeiro número não é divisível pelo segundo. Para verificar a divisibilidade do número lido por todos os números, basta testar número por número da sequência de 1 até o número lido, contando a quantidade de vezes que foi possível dividi-lo. Se ao final desse processo, o número foi divisível apenas por dois números (1 e ele mesmo), ele é primo, caso tenha sido dividido por mais de dois números, ele não é primo.

Para implementar esse algoritmo foi escolhida a linguagem PHP em homenagem ao matemático pokemaobr, que inclusive falou numa live que já esteve em uma competição de código mais eficiente para verificar se um número é primo durante a faculdade. A implementação dessa primeira solução é:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

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

if ($divisores == 2) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Para executar esse código, basta salvá-lo no computador, atribuir permissão de execução (exemplo: chmod +x verificaprimo), e executá-lo (./verificaprimo), visto que a primeira linha já informa ao sistema qual interpretador deve ser utilizado (essa linha é chamada de shebang). Caso essa linha não existisse, seria necessário chamar o código através do interpretador do PHP de forma explícita (php verificaprimo).

Em relação a eficiência, esse código verificará exatamente o mesmo número de divisões do número lido para dar a resposta se o número informado é primo ou não.

Segunda solução

A primeira solução funciona, porém para quem olha o código, existe um número mágico ($divisores == 2), que é proveniente da definição (o número deve ser divisível apenas por 1 e por ele mesmo), porém não faz muito sentido para quem não sabe ou não lembra do raciocínio que resulta nesse número. Como todos os números serão divisíveis por 1 e por ele mesmo, não é necessário fazer essa verificação, que pode ser assumida.

Para remover a verificação da divisibilidade pelo 1 e pelo próprio número, é necessário alterar a condição no for e ajustar o if final, considerando casos especiais que surgem com essa solução. Essas melhorias podem ser verificadas a baixo:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$divisores = 0;
for ($i = 2; $i < $numero; $i++) {
    if ($numero % $i == 0) {
        $divisores += 1;
    }
}

if ($divisores == 0 && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Em relação a eficiência, essa solução precisa fazer dois testes de divisibilidade a menos que a primeira solução, portanto um pouco mais eficiente, visto que não é necessário fazer a operação de divisão nesses casos (apenas a comparação). Porém não resolve de fato o problema do número mágico utilizado no código, apenas troca 2 por 0, o que já fica um pouco mais simples de ler, mas ainda é um número mágico para quem não acompanhar a lógica.

Terceira solução

Considerando que agora o algoritmo precisa verificar apenas se o contador $divisores foi incrementado alguma vez, é possível trocá-lo por um booleano. Para esse booleano fazer mais sentido, é possível utilizá-lo para dizer o estado do número, assumindo que ele é primo, até descobrir um divisor que prove que ele não é primo, resultando a seguinte implementação:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
for ($i = 2; $i < $numero; $i++) {
    if ($numero % $i == 0) {
        $primo = false;
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Essa solução remove totalmente o número mágico. Em relação a eficiência, a quantidade de verificações continua a mesma. Mas enquanto a segunda solução precisava ler o valor do contador $divisores, somar e guardar o novo valor nessa variável, nessa solução só o último passo (atribuir valor) é executado.

Quarta solução

Entretanto a terceira solução, mesmo após descobrir um caso que prova que o número lido não é primo, continua verificando todos os possíveis divisores. Porém uma vez que é descoberto um caso que prova que o número não é primo, não é necessário continuar verificando os demais. No código isso pode ser visto na variável $primo, que uma vez definida como false, não existe uma condição que a faça voltar para true, sendo possível criar uma interrupção no fluxo de execução (break), saindo do for sem verificar os demais divisores. Essa implementação fica assim:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
for ($i = 2; $i < $numero; $i++) {
    if ($numero % $i == 0) {
        $primo = false;
        break;
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

A eficiência do código continua a mesma para quando o número for primo. Porém quando o número não for primo, assim que for identificado o primeiro divisor, já se terá a resposta.

Quinta solução

Considerando que a divisão pode ser desfeita (função inversa) através de uma multiplicação, é possível descrever esse problema como a busca por dois números inteiros que multiplicados tem como resultado o número lido (a * b == $numero), também conhecido como fatoração. Testar todos os possíveis divisores, significa testar todos esses valores como a e verificar se o valor usado para b seria um número inteiro, onde o valor de b diminuirá conforme o valor de a crescer para que o número lido como resultado da multiplicação. Considerando a propriedade da comutatividade da multiplicação (a * b == b * a), existirá um ponto onde os valores de a e b são iguais e depois dele serão testados novamente as multiplicações já feitas, apenas trocando os valores de a e b. O ponto onde esses valores são iguais é a raiz do número lido (sqrt($numero) * sqrt($numero) == $numero), então só seria necessário verificar até ele, e não até o valor lido:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
for ($i = 2; $i <= sqrt($numero); $i++) {
    if ($numero % $i == 0) {
        $primo = false;
        break;
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Essa solução mantém a mesma eficiência para números não primos da anterior. Mas melhora para os números primos, visto que reduz os divisores testados.

Sexta solução

Embora a solução anterior seja boa, e muitos acabem sugerindo ela, existe algo a ser observado nela. Para cada vez que o for é executado, sua condição de repetição é avaliada, e assim calcula-se novamente a raiz do número ($i <= sqrt($numero)). O valor da raiz poderia ser guardado em uma variável, e utilizada essa variável para a comparação, visto que o resultado dessa função não muda conforme a execução do código, o que evitaria recalculá-la a cada verificação. Ficando assim:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
$raiz = sqrt($numero);
for ($i = 2; $i <= $raiz; $i++) {
    if ($numero % $i == 0) {
        $primo = false;
        break;
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Outras soluções

Ainda existem outras otimizações possíveis. Sabendo que o 2 é o único número primo par, seria possível verificar a divisão por ele, e após isso só testar divisores ímpares, reduzindo assim pela metade a quantidade de divisores testados (considerando também a otimização da raiz quadrada):

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
if ($numero != 2 && $numero % 2 == 0) {
    $primo = false;
} else {
    $raiz = sqrt($numero);
    for ($i = 3; $i <= $raiz; $i += 2) {
        if ($numero % $i == 0) {
            $primo = false;
            break;
        }
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Essas são otimizações considerando apenas o código. Ainda é possível considerar a arquitetura do computador onde ele será executando, buscando instruções mais rápida, ou que consomem menos energia (aumentando o tempo de bateria), para aquele processador. Outro tipo de otimização seria tentar reduzir a quantidade de memória utilizada, por exemplo, utilizando a variável que guarda o resultado para raiz como a variável de controle do for, percorrendo os números de forma inversa, como nessa implementação:

#!/usr/bin/env php
<?php
$stdin = fopen('php://stdin', 'r');

echo 'Digite um número: ';
$numero = trim(fgets($stdin));

$primo = true;
for ($i = floor(sqrt($numero)); $i > 1; $i--) {
    if ($numero % $i == 0) {
        $primo = false;
        break;
    }
}

if ($primo && $numero != 0 && $numero != 1) {
    echo "O número $numero é primo!\n";
} else {
    echo "O número $numero não é primo!\n";
}

fclose($stdin);

Considerações

Foi possível, partindo de uma solução não otimizada, fazer pequenas otimizações e chegar a uma solução bastante otimizada. Esse processo pode ser repetido em qualquer código, basta fazer uma solução simples que funciona, após isso estudar como melhorá-la, o que é um bom incentivo para voltar para o código depois dele ter funcionado.

Algumas otimizações melhoraram a legibilidade do código, deixando-o muito mais simples de entender posteriormente, removendo valores que parecem ser arbitrários do código (números mágicos). Enquanto outras otimizações aumentam a complexidade, criando uma escolha entre ter um código mais performático, ou mais fácil de entender.

Ainda sobre esse assunto, eu recomendo a palestra do Jon "MadDog" Hall no FISL 15, "Performance: More Than Just Speed":