# Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法是一种找质数的算法。我们知道，对于一个合数，那么它必定可以分解为两个质数相乘，比如21=3x7。那么我们也可以理解为，一个合数必定是一个质数的倍数，对于刚才的例子，21就是质数3的7倍（当然也可以说是质数7的3倍）。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 42
1 2 3 0 5 0 7 0 9 0  11 0  13 0  15 0  ... 42
1 2 3 0 5 0 7 0 0 0  11 0  13 0  0  0  ... 42
...


// 计算需要多少个字节, (n + 8)确保有足够的位
size_t length = (n + 8) >> CHAR_BIT_LOG;


#define CHAR_BIT_LOG 3
#define setbit(a, x) ((a)[(x) >> CHAR_BIT_LOG] |= 1 << ((x) & MASK))
#define isset(a, x) ((a)[(x) >> CHAR_BIT_LOG] & (1 << ((x) & MASK)))

for (int i = 2; i <= (int)floor(sqrt(n)); ++i) {
if (!isset(result, i)) {
int j = i*i;
while (j <= n) {
setbit(result, j);
j += i;
}
}
}


//
//  main.cpp
//  sieve
//
//  Created by BlueCocoa on 16/1/27.
//

#include <limits.h>
#include <iostream>
#include <functional>
#include <chrono>
#include <cmath>

using namespace std;

#define CHAR_BIT_LOG 3
#define setbit(a, x) ((a)[(x) >> CHAR_BIT_LOG] |= 1 << ((x) & MASK))
#define isset(a, x) ((a)[(x) >> CHAR_BIT_LOG] & (1 << ((x) & MASK)))

char * sieve(unsigned long long n) {
char * result = NULL;

if (n >= 2) {
// 计算需要多少个字节, (n + 8)确保有足够的位
size_t length = (n + 8) >> 3;
result = (char *)malloc(length);

memset(result, 0, length);
for (int i = 2; i <= (int)floor(sqrt(n)); ++i) {
if (!isset(result, i)) {
int j = i*i;
while (j <= n) {
setbit(result, j);
j += i;
}
}
}
}
return result;
}

template <class Return, class Param>
auto runtime(function<Return(Param)> func, Param param) -> Return {
Return result;
auto start = chrono::high_resolution_clock::now();
result = func(param);
auto end = chrono::high_resolution_clock::now();
printf("%lf\n", ((chrono::duration<double>)((end - start))).count());
return result;
}

int main(int argc, const char * argv[]) {
int upperbound = 42;
char * result = runtime<char *, unsigned long long>(sieve, upperbound);
for (int i = 2; i <= upperbound; i++)
if (!isset(result, i))
printf("%d ", i);
printf("\n");
free(result);
return 0;
}

声明: 本文为0xBBC原创, 转载注明出处喵～