30/09/2018, 18:09
Hỏi về thuật toán tối ưu liệt kế các số Nguyên Tố trong khoảng 1 đến 1 triệu
Đây là bài làm của em, nhưng chưa tối ưu, mong mọi người thông não… Cảm ơn mọi người
#include <stdio.h>
#include <math.h>
int main() {
int i, j, loop, count = 1, list[100000] = {2};
for(i=3; i<=1000000; i+=2) {
loop = floor(sqrt(i));
for(j=0; list[j]<=loop; ++j)
if( i % list[j] == 0 ) {
loop = 0;
break;
}
if( loop > 0 ) {
list[count] = i;
++count;
printf("%8d", i);
}
}
printf("
- Count: %d", count);
return 0;
}
Bài liên quan
Có thể xem qua: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://davidng94.wordpress.com/2015/03/15/check-prime-number
dùng sàng nguyên tố :