试除法判定质数

给定 n 个正整数 a_i，判定每个数是否是质数。

(试除法) O( \sqrt{n} )

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i < n;i ++){ //这个很好理解，从最小的质数2开始枚举到n - 1
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

这样写是无法通过全部案例测试的，会超时。

优化方法：可以只枚举到 \sqrt{n}

证明：

所以有下面这种写法。

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i <= sqrt(n);i ++){ //优化部分
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

这个为什么不推荐呢¿

因为，sqrt 这个函数运行很慢，每次执行时都要运算一遍，所以比较慢

但是这里竟然过了，离谱....

那我们这个算法也可以不用每次都算一遍sqrt，我们可以定义一个变量来存

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    int x = sqrt(n);
    for(int i = 2;i <= x;i ++){ //优化部分
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

比较推荐的方法i <= n / i

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){ //优化内容
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

分解质因数

给定 n 个正整数 a_i，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

分析

根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 n={p_1}^{a_1} * {p_2}^{a_2} {p_3}^{a_3}.....{p_n}^{a_n}

比如一个数16 在分解时先找到2这个质因子，然后由于 16/2后还可以 /2，所以会在2这个质因子上产生次方。

不优化版本：从 2~n 找到能整除的因子然后算次方

这里有个性质：n 中最多只含有一个大于 \sqrt{n}的因子。证明通过反证法：如果有两个大于 \sqrt{n}的因子，那么相乘会大于n，矛盾。证毕

于是我们发现最多只有一个大于 \sqrt{n}的因子，对其进行优化。先考虑比 \sqrt{n}小的，代码和质数的判定类似

最后如果n还是>1，说明这就是大于 \sqrt{n}的唯一质因子，输出即可。

#include <iostream>

using  namespace std;

int main()
{
  int n;
  cin >> n;
  while( n -- )
  {
    int x;
    cin >> x;
    for(int i = 2; i <= x / i; i++)
    {
      if( x % i == 0 )
      {
        int s = 0;
        while( x % i == 0 )
        {
          s++;
          x /= i;
        }
        cout << i << " " << s << endl;
      }
    }
    if( x > 1 )cout << x << " " << 1 << endl;
    cout << endl;
  }
  
  return 0;
}