Eratosthenes 筛法

【预备】素数计数函数Prime-counting function

在数学中，素数计数函数是一个用来表示小于或等于某个实数的素数的个数的函数，记为.

这个定理由高斯和勒让德在18世纪末提出，并在1896年被证明，证明用到了黎曼ζ函数的性质.

精确估计为：

一般使用：

换言之，第n个素数的大小约为O(nlogn),严格来说为

有上下界

给出简单证明

【预备】Mertens 第二定理

给出弱化版证明

证明

如果每一次对数组的操作花费 1 个单位时间，则时间复杂度为：

其中表示第k小的素数，根据Mertens第二定理，存在常数使得：

所以 Eratosthenes 筛法 的时间复杂度为O(nloglogn)

代码与实现

int Eratosthenes(int n) 
{int cnt = 0;//记录素数的数量，并不是必须的语句  is_prime[0] = is_prime[1] = 0;//预置认为0,1是素数for (int i = 2; i <= n; ++i){if (is_prime[i]) {prime[cnt++] = i;  // prime[cnt]是i,后置自增运算代表当前素数数量for (int j = i * i; j <= n; j += i)is_prime[j] = 0;  // 是i的倍数的均不是素数}}return cnt;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！