质数相关 - 简书

质数相关

1、质数

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数（素数）
（1）质数的判定-试除法 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++){//注意这里的优化
            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）分解质因数-试除法 O(sqrt（n))
从小到大枚举所有数，如果找到了他的一个约数，则while除尽，求出次数
当枚举到i的时候，n已经被除干净了，没有2~n-1中的质因子，所以不会出现合数
性质1：n中最多只包含一个大约sqrt(t)的质因子可以只枚举到sqrt(n) 用n/i 代替sqrt(n)优化
注意优化后还有判断n是否除尽（除尽则n为1），即判断是否存在那一个大于sqrtn的质因子单独处理
#include<bits/stdc++.h>
using namespace std;
int n,num;
void divide(int num){
for(int i=2;i<=num/i;i++){//根据性质优化
if(num%i==0){
int res=0;
while(num%i==0){
res++;
num/=i;
}
cout<<i<<' '<<res<<endl;
}

}
if(num>1) //单独处理那一个大于sqrt（n）的质因子
    cout<<num<<' '<<'1'<<endl;
    cout<<endl;

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

return 0;

}

（3）筛选质数
    选择n以内质数的个数
    核心操作：
    从前往后删掉a[i]的倍数
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代表质数总数 prime数组存放质数
        }
        for(int j=i+i;j<=n;j+=i){
            st[j]=1; //删除这个数的倍数
        }
    }
}
int main()
{
    cin>>n;
    select();
    cout<<cnt<<endl;
    return 0;
}
2、优化（只删除质数的倍数）
 埃式筛法

*/
//
//#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里筛，筛的都是质数的倍数
//              st[j] = true;
//      }
//  }
//}
//int main()
//{
//  cin >> n;
//  get_primes(n);
//  cout << cnt << endl;
//  system("PAUSE");
//  return 0;
//}
//
///*
//3、优化 线性筛法
//n只会被最小质因子筛掉
//因为pj存的是从小到大的质数
//1、当i%pj==0时
//pj一定是i的最小质因子，pj也一定是pj*i的最小质因子
//
//2、i%pj！=0；
//说明pj一定小于i的所有质因子，pj也一定是pj*i的最小质因子
//
//对于一个合数x，假设pj是x的最小质因子，当i枚举到x/pj时，  会被筛掉 
//*/
//#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;
//}