# 优化后的Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法初始化

Why on earth do we need even numbers while we pick primes

100以内的所有质数

t = (n - 2) >> 1

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

// 只保存奇数
length = (size_t)ceil(length / 2.0);

result = (char *)malloc(length);
memset(result, 0, length);
for (int i = 3; i <= (int)floor(sqrt(n)); i+=2) {
if (!isset(result, (i - 2) >> 1)) {
int j = i*i;
while (j <= n) {
setbit(result, (j - 2) >> 1);
// 因为i一定是奇数, 而j从i*i开始, 那么j也一定是奇数
// 又因为 奇数+奇数=偶数, 所以我们直接加上2*i来确保得到奇数
j += 2*i;
}
}
}


//
//  main.cpp
//  optimum sieve
//
//  Created by BlueCocoa on 16/1/28.
//

#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 & 0xF)以确保有足够的位
size_t length = n >> CHAR_BIT_LOG;
if (n & 0xF) length += 1;

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;
}

char * sieve2(unsigned long long n) {
char * result = NULL;
if (n >= 2) {
// 计算需要多少个字节, 检查(n & 0xF)以确保有足够的位
size_t length = n >> CHAR_BIT_LOG;
if (n & 0xF) length += 1;

// 只保存奇数
length = (size_t)ceil(length / 2.0);
result = (char *)malloc(length);
memset(result, 0, length);
for (int i = 3; i <= (int)floor(sqrt(n)); i+=2) {
if (!isset(result, (i - 2) >> 1)) {
int j = i*i;
while (j <= n) {
setbit(result, (j - 2) >> 1);
// 因为i一定是奇数, 而j从i*i开始, 那么j也一定是奇数
// 又因为 奇数+奇数=偶数, 所以我们直接加上2*i来确保得到奇数
j += 2*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 = 3; i < upperbound; i++) {
if (!isset(result, i)) {
printf("%d ", i);
}
}
printf("\n");
free(result);

result = runtime<char *, unsigned long long>(sieve2, upperbound);
for (int i = 0; i < upperbound / 2; i++) {
size_t prime = ((i<<1) + 3);
if (!isset(result, i) && (prime < upperbound)) {
printf("%zu ", prime);
}
}
printf("\n");
free(result);

return 0;
}


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