Vou colocar aqui 2 algoritmos para achar números primos. Um deles segue o principio de que todos os números primos achados vão para um array, e o outro é o algoritmo de Sieve of Eratosthenes, que utiliza uma array (supostamente binária) para marcar akeles que são primos.
Ambas as versões foram optimizadas por mim para conseguir melhores tempos. As sources estão em C++ (embora possam encontrar características de C simples no código). Se alguém tiver melhores ideias para os optimizar qualquer dos algoritmos, estão à vontade para postar o código (ou simplesmente a sugestão). Se alguém tiver dúvidas em relação ao código... pode perguntar tb.
#include <iostream>
#include <sys/time.h>
int main (int argc, char * const argv[]) {
int pos = 2, i, j, flag = 25, flagpos = 2, b = 1, c = 1, d = 1;
int* res = (int*) malloc(sizeof(int)*1000000);
struct timeval tv, tv2;
if (gettimeofday(&tv, NULL) == -1) {
std::cout << "Could\\'t start timer...n";
exit(-1);
}
res[0] = 2;
res[1] = 3;
for (i = 6; i <= 10000000; i+=6) {
for (j = 2; j < flagpos && !b; j++) {
if ((i - 1) % res[j] == 0)
c = 0;
if ((i + 1) % res[j] == 0)
d = 0;
}
if (b) {
res[pos] = i - 1;
pos++;
res[pos] = i + 1;
pos++;
}
else {
if (c) {
res[pos] = i - 1;
pos++;
}
if (d) {
res[pos] = i + 1;
pos++;
}
c = 1;
d = 1;
}
if (i + 1 == flag) {
flagpos++;
flag = res[flagpos]*res[flagpos];
pos--;
b = 0;
}
}
if (gettimeofday(&tv2, NULL) == -1) {
std::cout << "Could\\'t start timer...n";
exit(-1);
}
long hold = tv2.tv_sec - tv.tv_sec;
long time = 1000000 * hold + tv2.tv_usec - tv.tv_usec;
std::cout << pos + 1 << " prime numbers were found.n";
std::cout << "Time taken: " << time << " microseconds.n";
return 0;
}
#include <iostream>
#include <Math.h>
#include <sys/time.h>
#include <stdbool.h>
int main (int argc, char * const argv[]) {
int N, sqrtN;
std::cout << "Enter the number: ";
std::cin >> N;
struct timeval tv, tv2;
if (gettimeofday(&tv, NULL) == -1) {
std::cout << "Could\\'t start timer...n";
exit(-1);
}
N /= 2;
sqrtN = (int) sqrt(N);
char *res = (char*) calloc(N, sizeof(char));
int i, j, counter = 1;
for (i = 0; i < sqrtN; i++) {
if (!res[i]) {
counter++;
for (j = (3*i+3+(2*i+3)*i); j < N; j += (2*i+3))
res[j] = 1;
}
}
for (i = (int) sqrtN; i < N; i++)
if (!res[i]) counter++;
if (gettimeofday(&tv2, NULL) == -1) {
std::cout << "Could\\'t start timer...n";
exit(-1);
}
long hold = tv2.tv_sec - tv.tv_sec;
long time = 1000000 * hold + tv2.tv_usec - tv.tv_usec;
std::cout << "Time taken: " << time << " microseconds.n";
printf("%d prime numbers found.", counter);
free(res);
return 0;
}
Tópico: [C++] Algoritmo para achar números primos (Lida 3558 vezes)