1、質(zhì)數(shù)

在大于1的整數(shù)中，如果只包含1和本身這兩個約數(shù)，就被稱為質(zhì)數(shù)（素?cái)?shù)）
（1）質(zhì)數(shù)的判定-試除法 O(根號n)

#include<bits/stdc++.h>
using namespace std;
int n,num;
bool juge(int x){
    if(x<=1)
        return false;
    else{
        for(int i=2;i<=x/i;i++){//注意這里的優(yōu)化
            if(x%i==0)
                return false;
        }
    }
    return true;
}
int main()
{
    cin>>n;
    while(n--){
        cin>>num;
        if(juge(num))
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

    return 0;
}

（2）分解質(zhì)因數(shù)-試除法 O(sqrt（n))
從小到大枚舉所有數(shù)，如果找到了他的一個約數(shù)，則while除盡，求出次數(shù)
當(dāng)枚舉到i的時(shí)候，n已經(jīng)被除干凈了，沒有2~n-1中的質(zhì)因子，所以不會出現(xiàn)合數(shù)
性質(zhì)1：n中最多只包含一個大約sqrt(t)的質(zhì)因子 可以只枚舉到sqrt(n) 用n/i 代替sqrt(n)優(yōu)化
注意優(yōu)化后還有判斷n是否除盡（除盡則n為1），即判斷是否存在那一個大于sqrtn的質(zhì)因子 單獨(dú)處理
#include<bits/stdc++.h>
using namespace std;
int n,num;
void divide(int num){
for(int i=2;i<=num/i;i++){//根據(jù)性質(zhì)優(yōu)化
if(num%i==0){
int res=0;
while(num%i==0){
res++;
num/=i;
}
cout<<i<<' '<<res<<endl;
}

}
if(num>1) //單獨(dú)處理那一個大于sqrt（n）的質(zhì)因子
    cout<<num<<' '<<'1'<<endl;
    cout<<endl;

}
int main()
{
cin>>n;
while(n--){
cin>>num;
divide(num);
}

return 0;

}

（3）篩選質(zhì)數(shù)
    選擇n以內(nèi)質(zhì)數(shù)的個數(shù)
    核心操作：
    從前往后刪掉a[i]的倍數(shù)
1、樸素篩法
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e6+10;
int prime[N];
int st[N];
int cnt;
void select(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[cnt++]=i;//cnt代表質(zhì)數(shù)總數(shù) prime數(shù)組存放質(zhì)數(shù)
        }
        for(int j=i+i;j<=n;j+=i){
            st[j]=1; //刪除這個數(shù)的倍數(shù)
        }
    }
}
int main()
{
    cin>>n;
    select();
    cout<<cnt<<endl;
    return 0;
}
2、優(yōu)化（只刪除質(zhì)數(shù)的倍數(shù)）
 埃式篩法

*/
//
//#include<bits/stdc++.h>
//using namespace std;
//int n;
//const int N = 1e6 + 10;
//int prime[N];
//int st[N];
//int cnt;
//void get_primes(int n) {
//  for (int i = 2; i <= n; i++) {
//      if (!st[i]) {
//          prime[cnt++] = i;
//          for (int j = i; j <= n; j += i) //在這個if里篩，篩的都是質(zhì)數(shù)的倍數(shù)
//              st[j] = true;
//      }
//  }
//}
//int main()
//{
//  cin >> n;
//  get_primes(n);
//  cout << cnt << endl;
//  system("PAUSE");
//  return 0;
//}
//
///*
//3、優(yōu)化 線性篩法
//n只會被最小質(zhì)因子篩掉
//因?yàn)閜j存的是從小到大的質(zhì)數(shù)
//1、當(dāng)i%pj==0時(shí)
//pj一定是i的最小質(zhì)因子，pj也一定是pj*i的最小質(zhì)因子
//
//2、i%pj！=0；
//說明pj一定小于i的所有質(zhì)因子，pj也一定是pj*i的最小質(zhì)因子
//
//對于一個合數(shù)x，假設(shè)pj是x的最小質(zhì)因子，當(dāng)i枚舉到x/pj時(shí)，  會被篩掉 
//*/
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e6 + 10;
//int prime[N], vis[N], n, cnt;
//int main()
//{
//  cin >> n;
//  for (int i = 2; i <= n; i++) {
//      if (!vis[i])
//          prime[cnt++] = i;
//      for (int j = 0; prime[j] <= n / i; j++) {
//          vis[prime[j] * i] = 1;
//          if (i%prime[j] == 0)break;
//      }
//  }
//  cout << cnt << endl;
//  return 0;
//}