算法学习-eratosthenes筛法求素数

题目

给定正整数N，求小于等于N的全部素数。

eratosthenes筛法

将2到N写成一排；记派头元素为x，则x是素数；除x以外，将x的倍数全部划去；重复以上操作，知道没有元素被划去，则剩余的即小于等于N的全部素数为表述方便，将派头元素成为“筛数”。

代码如下，对于N我们只需筛带小于N的开方的那个整数就行，对于筛数i，i以前的倍数就不用筛了，因为之前就已经筛过了

void Eratosthenes(bool* a, int n) { a[1] = false;// a[0]不用 int i; for (i = 2; i <= n; i++)// 筛法，默认都是素数 { a[i] = true; } int p = 2;// 第一个筛孔 int j = p*p; int c = 0; while (j <= n) { while (j <= n) { a[j] = false; j += p; } p++; while (!a[p]) p++; j = p*p; } }