### 问题描述 从2开始到n-1都不能整除则为素数。 ### 优化 1. 从2到sqrt(n)不能整除就可以 1.  通过对被2、3和5整除的特殊检验，避免了近3/4的开方运算，其次，只考虑奇数作为可能的因子，在剩余的数中避免了大约一半的整除检验（注意一点，2，3，5本身也是素数）（If( n%2 == 0 ) return (n==2); //能被2整除且不是2本身的不是素数） 1. 用乘法运算代替开方运算 ~~~ int prime(int n) { if(n%2==0)return (n==2); if(n%3==0)return (n==3); if(n%5==0)return (n==5); for(int i=7; i*i<=n; i+=2) if(n%i==0)return 0; return 1; } ~~~ ### 简单的埃氏筛法 实现简单的埃氏筛法（Sieve of Eratosthenes）来计算所有小于n的素数。这个程序的主要数据结构是一个n比特的数组，初始值都为真。每发现一个素数时，数组中所有这个素数的倍数就设置为假。下一个素数就是数组中下一个为真的比特。 ### 解析 下面的C程序实现了埃氏筛法来计算所有小于n的素数。其基本数据结构是n比特数组x，初始值全部为1。每发现一个素数，数组中所有它的倍数都设为0。下一个素数就是数组中的下一个取值为1的比特位。 ~~~ #include <iostream> using namespace std; int main( ){ int i, p, n; char x[100001];  n = 100000; for (i = 1; i <= n; i++) x[i] = 1; x[1] = 0; //1不是素数 p = 2; //第一个素数 while (p <= n){ cout<<p<<" "; for (i = 2*p; i <= n; i = i+p) x[i] = 0; do p++; while (x[p] == 0); //得到第一个标记为1的数，为素数 } } ~~~ **转载请注明出处**：[http://blog.csdn.net/utimes/article/details/8863999](http://blog.csdn.net/utimes/article/details/8863999)