埃氏筛法之素数

本文主要是介绍埃氏筛法之素数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理：

首先将2~n个数记录下来，2作为最小素数，所以2的倍数不是素数，从记录中划去，扫一遍之后，将3作为最小素数，3的倍数划去，如此下去，求出所有素数。如表格所示：

2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2	3	-	5	-	7	-	9	-	11	-	13	-	15	-	17	-	19	-
2	3	-	5	-	7	-	-	-	11	-	13	-	-	-	17	-	19	-

代码：

判断是否是素数：

bool is_prime(int n){for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return n!=1;
}

埃氏筛法：

const int MAX  = 1000;
int prime[MAX];
bool is_prime[MAX];int sieve(int n){int p=0;for(int i=0;i<=n;i++)is_prime[i] = true;is_prime[0] = is_prime[1] = false;for(int i=2;i<=n;i++){if(is_prime[i]){prime[p++] = i;for(int j=2*i;j<=n;j+=i)  is_prime[j] = false;}}return p;
}

这篇关于埃氏筛法之素数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---