质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它自身外，不能被其他自然数整除的数称为质数。否则称为合数
合数（Composite number），指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
1既不属于质数也不属于合数。最小的合数是4。最小的素数是 2 。
因数：假如a*b=c（a、b、c都是整数)，那么我们称a和b就是c的因数。反过来说，我们称c为a、b的倍数。
第11 题的核心：写一个函数 用来判断一个数是否为素数 根据素数定义，代码如下： bool Is_prime(int n) //如果 n 是素数返回真，否则返回假。注意：n 必须是大于等于2 的，因为2 是最小的素数了。{ if(n<2) return false; int i; for(i=2; i<n; i++) //从2 开始直到 n-1，如果n 除以i 余数为0(n被i整除)，则n 就不是素数，如果都除不尽，则符合定义是素数。 if(n%i == 0) return false; return true;}理解了上面的代码后，发现for 循环在遇到素数时 总是要循环到n-1，那如果n 很大呢，检测的效率可能就不令人满意了。
所以要在不影响准确性的前提下，尽量减少循环次数，提高效率。首先想到了 i<=n/2，因为n 除以比它的一半还大的数 肯定除不尽。
其实还有更好的方法，只要 i<= n的算术平方根 就行了，原理是判断n 是否是合数，如果不是合数就一定是素数了。
而一个数如果是合数，那么除了1 之外 还至少有一个因子 是小于等于它的平方根的，等于平方根的情况就是这个合数是一个素数的平方，比如 4，9，25，49等，n 把小于等于它的平方根的数全除以一遍后 都除不尽，则n 不是一个合数，所以可以判定n 为素数。
原谅我说了一堆废话，其实只要明白基本的定义就行了，数学上很多东西都是只需死记，不需要深入研究，因为公式、定理都是科学家们证明过的，我们只需要拿来用就行了。
虚心的棉花糖筛法
要得到自然数n以内的全部素数，必须把不大于根号 n的所有素数的倍数剔除，剩下的就是素数。
代码如下：
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cmath> #include <ctime> #include <cstdlib> #include <cstdio> using namespace std; //小白阶段，库文件太乱。int main(){ cout<< "请输入一个整数，程序输出1到这个数的所有素数：n"; int n; while(cin>>n) { vector<bool> a(n); // n个bool 类型的向量a int i,j; for(i=2; i<n; i++) //初始全部标记为真 a[i]= true; for(i=2; i*i<n; i++) //筛选过程，根据方法的定义理解 if(a[i]) for(j=i; i*j<n; j++) a[i*j]= false; for(i=2; i<n; i++) //仍然为真的元素的下标就是素数 if(a[i]) cout<<i<<'t'; } return 0; }第15题：输出前N个素数 一种方法是根据第11题所写的判断素数的函数，用循环从2 开始逐个判断，直到输出了N 个素数后停止循环。 但是逐个判断的方法效率 没有上面的筛选法效率高，问题是筛选时需要先指定一个确切的范围，而前N个素数的最小范围是多少呢，下面这个公式就能求出 前N个素数的上界： pn<nlnn+nlnlnn(n≥6) 有了范围就能利用上面的筛选法 求解了。 先写到这，公式别处看的，百度一下就有了。