C++ 101 – Parte 5 – Arrays e o Crivo de Eratóstenes

Olá pessoal, tudo certo?

O blog ficou parado alguns dias. Isso ocorreu devido ao TechEd – onde tive a honra de participar, de forma potencializada, pela primeira vez, como palestrante; ao esquenta na Global Code; ao meu primeiro PZGeek; ao meu primeiro Community Zone; ao voidpodcast #11 (o melhor que já fizemos, IMHO); e muito trabalho.

Falando em trabalho, confesso-me surpreso e grato pela oportunidade de continuar vivendo experiências novas e incríveis – conhecendo pessoas e empresas fascinantes – mesmo depois de tantos anos na mesma empresa.

No post de hoje, falo sobre Arrays em C++ através de uma implementação do (clássico) Crivo de Eratóstenes.

Se você chegou agora, consulte os posts anteriores.

Arrays em C++

Usar vetores em C++ é bem simples. Observe:

#include ;

using std::cout;
using std::endl;
void main()
{
        int a[5];
        a[0] = 5;
        a[1] = 7;
        a[2] = 3;
        a[3] = 9;
        a[4] = 10;

        for (int i = 0; i < 5; i++)
        {
                cout << a[i] << endl;
        }
}

Como você pode ver, a declaração do vetor foi suficiente para alocar a memória (repare nas diferenças para o C#).  Agora, uma versão alternativa:

include ;

using std::cout;
using std::endl;
void main()
{
        int a[] = {5, 7, 3, 9, 10};
        
        for (int i = 0; i < 5; i++)
        {
                cout << a[i] << endl;
        }
}

Arrays também podem ser acessados usando a notação de ponteiros (que já conhecemos). Observe:

#include ;

using std::cout;
using std::endl;
void main()
{
        int a[] = {5, 7, 3, 9, 10};
        
        for (int i = 0; i < 5; i++)
        {
                cout << *(a + i) << endl;
        }
}

Lindo, não!? Há quem diga que C++ é feia.

Crivo de Eratóstenes

Agora que já sabemos usar vetores, vamos escrever um código bacana. Trata-se do Crivo de Eratóstenes : um algoritmo clássico para identificar números primos. Eis minha implementação:

#include ;

using std::cout;
using std::endl;

static const int N = 1000;

void main()
{
        long i, a[N];
        for (i = 2; i < N; i++) a[i] = 1;

        for (i = 2; i < N; i++)
                if (a[i])
                        for (int j = i; (j * i) < N; j++)
                                a[i * j] = 0;

        for (i = 2; i < N; i++)
                if (a[i])
                        cout << " " << i;

        cout << endl;
}

O objetivo desse código é manter todos os elementos do vetor com índices correspondentes a números primos, com um, todos os demais com zero. Para isso:

1. inicializo todos os elementos do vetor com 1;
2. modifico todos os “múltiplos” de primos para 0 (são não-primos);

Importante observar que, como utilizamos apenas os valores 0 e 1, poderíamos produzir uma versão mais eficiente com um mapa de bits… Mas esse, é tema para um outro post.