[C++] Algoritmo para achar números primos

[KTachyon]

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.

Code Select Expand

#include

#include



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;

}

Code Select Expand

#include

#include

#include

#include



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;

}

[Ghetto_Smurf]

xiiiiiiiiii e eu que so percebo de pascal fico á nora com esses codigos : rir :