分解质数

原题链接: 试除法判定质数

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int x){
  if(x<2) return false;//0，1不是质数，直接返回

  for(int i = 2;i <= x/i;i++){//只看到根号x即可，后面的数重复了
    if(x % i == 0){//如果能除开说明是合数不是质数
      return false;
    }
  }
  return true;
}

int main(){
  int n;
  cin >> n;
  while(n--){
    int a;
    cin >> a;
    if(is_prime(a)){
      cout << "Yes" <<endl;
    }else{
      cout << "No" <<endl;
    }
  }
}

分解质因数

原题链接: 试除法分解质因数

#include <bits/stdc++.h>
using namespace std;

void divide(int x){
  for(int i = 2;i <= x / i;i++){//依旧拆分
    if(x % i == 0){//如果能被i整除
      int s = 0;
      while(x % i == 0) x/=i,s++;//看看能整除几次，代表了另外一个因数
      cout << i << " " << s<<endl;
    }
  }
  if(x>1) cout << x << " " << 1<<endl;//如果最后x>1说明x本身是个质数，输出1和他自己
  cout << endl;
}

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

筛质数

原题链接: 筛质数

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int primes[N],cnt;//记录质数
bool st[N];//判断是否筛过
void get_primes(int n){
  for(int i = 2;i <= n;i++){//从2开始筛到n
    if(!st[i]) primes[cnt++]=i;//如果i没被筛，把i加入到素数列表中，同时cnt++
    for(int j = 0;primes[j] <= n/i;j++){//避免越界
      st[primes[j] * i] = true;//如果素数列表中的数乘以当前的数没晒，那么直接判定他不是质数，因为两质数相乘是合数
      if(i%primes[j] == 0)break;//如果i能被素数整除了，说明此时存在更大的数可以和当前素数进行配对来筛更多的数，i已经和这个素数走到头了
    }
  }
}
int main(){
  int n;
  cin >> n;
  get_primes(n);
  cout << cnt << endl;
}

求约数

原题链接: 试除法求约数

#include <bits/stdc++.h>
using namespace std;

vector<int> divisor(int n){
  vector<int> res;
  for(int i = 1;i <= n / i;i++){//这里从1开始，因为1也可能是约数的一部分
    if(n % i == 0){//如果能被i整除，说明i是一个约数
      res.push_back(i);
      if(i != n / i){//如果i * i != n 那说明另外一个约数也找到了就是n/i
      //因为这里只遍历到了根号n，所以不用担心重复
      //例如6，当i=2时加入了2、3
      //理论上当i=3时会重复加入，但是i不会取到3，因为根号六小于三
        res.push_back(n/i);
      }
    }
  }
  return res;
}

int main(){
  int m;
  cin >> m;
  while(m--){
    int a;
    cin >> a;
    auto c = divisor(a);
    sort(c.begin(),c.end());//对约数列表进行排序
    for(auto a:c){//遍历约数
      cout << a << " ";
    }
    cout << endl;
  }
}

约数个数

N = p1^c1 * p2^c2 * … *pk^ck
公式： (c1 + 1) * (c2 + 1) * … * (ck + 1)
也就是指数加一并相乘

原题链接: 约数个数

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int main(){
  int T;
  cin >> T;
  unordered_map<int,int> h;//开一个哈希表来存储底数和指数
  while(T--){
    int n;
    cin >> n;
    for(int i = 2;i <= n/i;i++){//看约数
      while(n % i == 0){//看这个约数的最大指数
        h[i]++;
        n/=i;
      }
    }
    if(n>1) h[n]++;//如果n>1那么n的质数也++
  }
  long long res = 1;//初始化答案为1
  for(auto i = h.begin();i!=h.end();i++){//遍历哈希表
    res = res*(i->second + 1) % mod;//取第二个数加一并相乘
    //过程中取模防止中途爆
  }
  cout << res << endl;
}

约数之和

N = p1^c1 * p2^c2 * … *pk^ck
公式:(p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

原题链接: 约数之和

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int main(){
  int T;
  cin >> T;
  unordered_map<int,int> h;//依旧开哈希表
  while(T--){
    int n;
    cin >> n;
    for(int i = 2;i <= n/i;i++){//找因数
      while(n%i==0){
        h[i]++;
        n/=i;
      }
    }
    if(n>1) h[n]++;
  }

  long long res = 1;
  for(auto item : h){//遍历哈希表，这里是增强for循环
    int x = item.first,y = item.second;//取出每一个值的底数和指数
    long long t = 1;//定义一个临时变量
    while(y--){
      t = (t * x + 1) % mod;//根据公式求得当前的最终结果
    }
    res = res * t %mod;//累乘答案
  }
  cout << res << endl;
}

关于代码和公式的形式不太一样，是因为代码用了数列的思想，拆分了一下，具体我也不是很清楚，有大佬可以在评论区讲解一下吗？