Números primos em C++ - Como descobrir

Neste tutorial, vamos destrinchar os primos. Vamos aprender como verificar se um número é primo ou não, bem como exibir uma lista de quantos primos quisermos, usando laços e loopings, em C++.

Números Primos na Matemática

Um número é dito ser primo quando pode ser dividido somente por 1 e por ele mesmo.
O 7 é primo, você pode dividir só por 1 e por 7, por qualquer outro valor vai dar um resultado quebrado.

O 12 não é primo, pois pode ser dividido por 1, 2, 3, 4, 6 e 12.

Vejamos alguns números primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997...

Os primos são uma classe muuuuito especial na Matemática, tendo utilidade em diversos ramos e áreas, como na criptografia.

Vale a pena pesquisar sobre eles, há todo um véu de mistério neles, pois tentam há milênios encontrar uma fórmula para gerar números primos e nada até hoje deu certo.

Será que um dia você consegue? Quem sabe...se ganhar o prêmio Nobel, não esquece de compartilhar a grana com a gente...

Simbora caçar uns primos?

Como Descobrir se um número é primo

Para verificar se um número num é primo, basta verificar seus divisores, de 1 até num.

Por exemplo, vamos testar se o 9 é primo. Basta analisar o resto da divisão por 1, 2, 3, 4, 5, 6, 7, 8, e 9.
Se for primo, somente vai ser divisível por 1 e por ele mesmo, logo vai ter 2 divisores. Mas o resto da divisão vai dar 0 quando fizermos 9%3, logo 3 também é divisor, totalizando 3 divisores, logo não é primo.

Agora o 11.
Podemos pegar o resto da divisão por 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 e 11, que só vai dar 0 pra 1 e pra 11.
Logo, ele é primo.

Ou seja, basta fazer o resto da divisão de num por 1, 2, 3, 4, 5, ..., até num, e contar na variável div (inicializada com 0), quantos divisores tem.

Se for 2, é primo.
Se for mais que 2, não é primo.

Veja o código:

#include <iostream>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=1 ; aux<=num ; aux++)
        if(num%aux==0)
            div++;

    if(div==2)
        cout<<"É primo"<<endl;
    else
        cout<<"Não é primo"<<endl;
    return 0;
}

Testamos com um número primo gigante, o 479001599.
Aqui levou 1.831s pra verificar, e na sua máquina?

Otimizando a busca por primos

Ora, todo número é divisível por 1.
Então não precisamos fazer o resto da divisão por 1, já é uma checagem a menos.

E também não precisamos testar até num.
Passou da metade, não vai ter mais nenhum divisor possível.

Dando uma enxugada no código, ele fica assim:

#include <iostream>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=2 ; aux<=num/2 ; aux++)
        if(num%aux==0)
            div++;

    if(div==0)
        cout<<"É primo"<<endl;
    else
        cout<<"Não é primo"<<endl;
    return 0;
}

Agora levou só 1.012s
E na sua máquina?

Podemos ir mais além e calcular até a raiz quadrada de num, ao invés de apenas até num/2 (pesquise o motivo disso):

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=2 ; aux<=sqrt(num) ; aux++)
        if(num%aux==0)
            div++;

    if(div==0)
        cout<<"É primo"<<endl;
    else
        cout<<"Não é primo"<<endl;
    return 0;
}

0.004s ! Carai, maluco!

Achando primos num intervalo

Agora vamos imprimir todos os primos num determinado intervalo, de 1 até um valor Máximo, como 100.

Primeiro, uma variável pra testar todos os números de 2 até Max, é a aux.

Para cada número, vamos contar todos os divisores e armazenar na variável div, por isso ela deve começar zerada dentro do primeiro laço.

No segundo FOR, vamos verificar cada número aux, fazendo o resto da divisão deles por 2 até raiz quadrada do número, para verificar se tem divisores.

Se tiver, cai no IF (IF dentro de um FOR que está dentro de outro FOR, que loucura!), que incrementa div.

Após toda essa verificação interna, ele é primo se div tiver 0 como valor, se tiver, então imprimimos o valor de aux, pois é um primo.

Veja como fica o código:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int aux, coun, Max=100, div;

    for(aux=2 ; aux<=Max ; aux++){
        div=0;

        for(coun=2 ; coun<=sqrt(aux) ; coun++)
            if(aux%coun==0)
                div++;

        if(!div)
            cout<<aux<<" ";
    }

    cout<<endl;

    return 0;
}

Teste com mil, 10 mil, 1 milhão...só agora você tem real noção do poder e capacidade de calcular que tem sua máquina