输入一个整数n，输出不大于它的质数的个数。
这是一个经典的问题。不管用什么算法，思路都是嵌套循环，对小于n的自然数判断是否质数。
代码不好贴，就截图了。文末面有源码链接。
基础版
最笨的办法就是按顺序分别判断：//基础版
int primeNum_0(int n)
{
int div;//试除变量
int count = 0;//质数个数
for (int i = 2; i <= n; ++i)
{
for (div = 2; div < i; ++div)
{
if (i % div == 0)//不是质数
break;
}
if (div == i)//质数
++count;
}
return count;
}
测试输出：
There are 9592 prime numbers in 99999.
Completed with 1429 ms.
升级版
//升级版
int primeNum_1(int n)
{
int div, count = 0;
for (int i = 2; i <= n; ++i)
{
//试除上限为i的平方根取较大整数
int top = floor(sqrt(i)) + 1;
for (div = 2; div < top; ++div)
{
if (i % div == 0)
break;
}
if (div >= top)
++count;
}
return count;
}
这里对比上面的基础版，尽管代码有些变化，但可以看出它们仅有的区别就是当试除i的数div大于√i时，就不再继续试除，而判定i为质数。
这里利用了数本身的性质：如果一个数i可以被不小于√i的整数整除，那么得到的商一定是不大于√i的整数。因此，在试除到√i时便可以判定i是否为质数了。
这样一步操作，使运算的次数大大减少。
测试输出：
There are 9676 prime numbers in 99999.
Completed with 24 ms.
There are 665107 prime numbers in 9999999.
Completed with 5680 ms.
对于输入99999，对比基础版的超过1秒的运算时间，升级版只用了不到0.1秒。
升级改良版
在升级版的基础上，还可以改进。
//升级改良版
int primeNum_2(int n)
{
int div, count = 1;//2直接算作质数
for (int i = 3; i <= n; i = i + 2)
{
//因为试除从3开始，2的试除单独提出来
if(i % 2 == 0)
continue;
int top = floor(sqrt(i)) + 1;
for (div = 3; div < top; div = div + 2)
{
if (i % div == 0)
break;
}
if (div >= top)
++count;
}
return count;
}
这个版本相对于升级版又有了一些改动：试除从3开始，每次步进2。因为从循环里是3开始的，所以对于2的试除单独放出来(减少避免在循环中增加条件判断)，不影响性能。同时这样3也无法正常计算了，索性把3也提前算上，count初始化为2。
这里的原理也很简单：任何大于2的偶数不可能是质数。为了应用这个原理，有了上面的改动，虽然代码变得有些畸形，不过速度却相对提升了接近一倍。
其实这里还有个bug，当输入1或者2的时候也会输出有两个质数。可以在循环外加上条件判断，单独处理，只是这样代码会不那么美观。事实上这个算法在设计上本身也很不完美，博主还没有学过算法，很多不规范的地方请谅解。
测试输出：
There are 9674 prime numbers in 99999.
Completed with 0 ms.
There are 665105 prime numbers in 9999999.
Completed with 2826 ms.
这里99999的输入已经可以在1毫秒之内解决了，9999999用了接近3秒，和升级版的5秒多相比有了不错的提升。
从速度上来看，99999从20多毫秒提升到1毫秒，二十多倍，而9999999却只是加快了两倍左右，这或许和CPU的多任务机制有关，相关内容不怎么熟悉，就不解释了。因此用执行时间来反应算法速度并不很科学，或许用变量记录最内层循环执行的次数会更好。
豪华版
//豪华版
int primeNum_3(int n)
{
int count = 1;
int maxSize;//最大存储质数的个数
//申请内存
if(MAX_SIZE < ceil(sqrt(n)))
maxSize = MAX_SIZE;
else
maxSize = (int)(sqrt(n));
int* primeNums = (int*)malloc((maxSize * sizeof(int)));
primeNums[0] = 2;//2先放进去
int size = 1;//当前存储的质数个数
int div, cur, top;
for (int i = 3; i <= n; ++i)
{
top = ceil(sqrt(i));//试除上限
cur = 0;//当前试除数在存储空间的位置
div = primeNums[cur];
while (i % div != 0)
{
if (div >= top)
{
if (size < maxSize)//判断存储空间是否已满
primeNums[size++] = i;//将质数加入存储数组
++count;
break;
}//找到质数
//若已试除到存储空间最后一个数，步进2
if (cur < size - 1)
div = primeNums[++cur];
else
div += 2;
}
}
free(primeNums);
return count;
}
还有一个可以利用的性质，对于正整数i，如果i 可以被div整除(div为小于i且大于2的非质数)，那么i一定存在小于div的质数可以整除i，因为非质数div可以被分为若干质数的乘积。
而我们判断一个数是否是质数是从2开始去试除这个数(即使这个判断被单独列出)，而2是最小的质数，因此要判断一个大于2的正整数i是否是质数，只需要判断是否存在一个数k可以整除i，其中k是[2,√i]区间内的质数。
因此，我们可以建立一个质数存储表。每当判断出一个数是质数时，就把这个数加入表中。因为我们是从小到大开始判断，所以这个表也是从小到大的。然后对于一个数i，只需用这个表中不大于√i的质数去试除i，如果最后一不大于√i的质数都无法整除i，那么i是一个质数。
这个方法比上一种快一些，但消耗的空间也大得多。
测试程序
int main()
{
int n = 0;
scanf("%d", &n);
if(n < 2)
return 0;
int result, timeCount;//计时
if(n <= 100000)
{
timeCount = clock();
result = primeNum_0(n);
timeCount = clock() - timeCount;
printf("%d 个质数，基础版，%d 毫秒\n", result, timeCount);
}//数值太大基础版耗时太久
timeCount = clock();
result = primeNum_1(n);
timeCount = clock() - timeCount;
printf("%d 个质数，升级版，%d 毫秒\n", result, timeCount);
timeCount = clock();
result = primeNum_2(n);
timeCount = clock() - timeCount;
printf("%d 个质数，升级改良版，%d 毫秒\n", result, timeCount);
timeCount = clock();
result = primeNum_3(n);
timeCount = clock() - timeCount;
printf("%d 个质数，豪华版，%d 毫秒\n", result, timeCount);
//system("pause");
}