苍茫大地一剑尽挽破，何处繁华笙歌落。斜倚云端千壶掩寂寞，纵使他人空笑我。

素数（Prime Number）定义：

素数又称质数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数，举个栗子：2 ，3 ，5，7，……；那么剩下的就可以称为合数了。

数学家认为素数是最重要的数，因为所有别的数都可以由若干个素数相乘而得，它是数学中的原子。比如8可以由2*2*2得到，15可以是由3*5得到……

素数有啥用？？？

质因数分解（唯一分解定理）基本概念：

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数。

并且，每个合数能够且仅仅能够被分解为唯一一组质因数的乘积。

密码学，公钥密码，加密算法、安全认证等方面,质数都是在素数（质数）的层面上进行研究。

怎么求？？？

先看看万能暴力：

#include<stdio.h> #include<time.h> int IsPrime(int n) { int i; if(n <= 1){ return 0; } if(n==2){ return 1; } for(i = 2;i <n/2;i++){ if(n%i==0) return 0; } return 1; } int main() { int n,i; double t1 = clock(); for(i = 0;i<=200000;i++){ if(IsPrime(i)) ;//printf(" %d ",i); } double t2 = clock(); printf("\n运行时间：%fs\n",(t2-t1)/1000.0); }

普通筛选法--埃拉托斯特尼筛法O(nloglogn)

void init() { int i,j; for(i = 2;i <=N ;i++){ prime[i] = 1; } for(i = 2;i <= N;i++){ if(prime[i]) printf(" %d ",i); for(j = i+i;j <= N;j += i) prime[j] = 0; } }

PS：因为6在i==2时就被标记了，而在i==3的时候又被标记了一次，所以还是有改进的空间。

线性筛选法——欧拉筛法：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<iomanip> #include<set> #include<map> #include<vector> #include<queue> #include<stack> #define inf 1000000007 typedef long long ll; using namespace std; int f[1000005]; int main() { int n,t=0; scanf("%d",&n); f[1]=0; for(int i=2;i<=n;i++) f[i]=1; for(int i=2;i<=n;i++) { if(f[i]==1) { for(int j=2;j*i<=n;j++) f[i*j]=0; } } for(int i=2;i<=n;i++) if(f[i]) t++; printf("%d ",t); }