Projeto de Programação 1
Crivo de Eratóstenes Paralelo usando MPI

O Crivo de Eratóstenes é um algoritmo supreendentemente eficiente para encontrar números primos até um valor limite pré-definido. Tal algoritmo teria sido criado pelo matemático grego Eratóstenes (285-194 a.C.) que, entre outras proezas, foi o terceiro bibliotecário chefe da Biblioteca de Alexandria e o primeiro a calcular a circunferência da Terra.

Um número primo é um número natural que tem exatamente \(2\) divisores distintos: \(1\) e ele mesmo.

O crivo de Eratóstenes é um método para encontrar todos os números primos até um número limite \(n\). O método pode ser descrito pelos seguintes passos¹:

1. Crie uma lista de inteiros consecutivos de \(2\) até \(n\): (\(2, 3, 4, \ldots, n\)).
2. Seja \(p = 2\), o primeiro número primo.
3. Enumere todos os múltiplos de \(p\) até \(n\) e marque-os como não primos na lista criada no primeiro passo. Esses números serão da forma \(2p, 3p, 4p,\ldots\) Note que \(p\) deve continuar na lista (pois é primo).
4. Encontre o primeiro número na lista que seja maior do que \(p\) e que não esteja marcado como não primo. Caso não exista tal número, pare. Caso contrário, seja \(p\) igual a este número (que é o próximo primo já que caso não fosse primo ele teria sido marcado no passo 3), repita a partir do passo 3.
5. Quando o algoritmo terminar, os números não marcados presentes na lista serão todos os números primos entre \(1\) e \(n\).

Note que algoritmo pode marcar alguns números mais do que uma vez, por exemplo, 15 vai ser marcado tanto pelo 3 quanto pelo 5.

Este projeto² tem dois objetivos. O primeiro objetivo é implementar uma versão paralela do Crivo de Eratóstenes utilizando MPI e a linguagem de programação C. O segundo objetivo é analizar o desempenho das implementações apresentadas. Observe como o speedup e a eficiência variam com a adição de processadores e com o tamanho do problema.

O seu programa deverá receber como entrada \(N\) (o limite superior até o qual todos os números primos deverão ser gerados) e ter como saída a quantidade de números primos encontrados no intervalo \([1, n]\).

As execuções de teste serão feitas em máquinas paralelas com até 64 processadores (\(1 \le P \le 16\)) e com \(N\) variando desde \(10^6\) até \(10^{11}\).

Seu programa deve ser capaz de funcionar no mínimo com \(N = 10^6\).

---

Todos as entregas descritas abaixo devem ser feitas via repósitório no GitHub. Para criar o reposítório acesse: https://classroom.github.com/g/SJPvp8Du

Para dúvidas gerais sobre o projeto crie um issue em: https://github.com/ufabc-bcc/2019.Q1.PP.Projeto1.MPI Atenção, este repositório e issues são visíveis a TODOS os grupos.

Para dúvidas específicas sobre o seu projeto, seu código ou que contenham informações sensíveis (que você não quer que os outros grupos tenham acesso), crie um issue no seu próprio repositório.

A avaliação levará em conta não apenas o resultado final entregue, mas também todo o processo para chegar no resultado. Este processo será avaliado pelos commits no repositório do GitHub. Usuários com poucos ou nenhum commit receberão notas inferiores àqueles com alta participação. A avaliação não levará em conta o número de commits mas sim a sua relevância e a sua regularidade. Por exemplo, um commit que serviu apenas para colocar um espaço entre 1+2 para transformá-lo em 1 + 2 não será considerado.