算法知识-数论小记
试除法判定质数123456789101112int n;int a;bool pr(int a){ if(a < 2) return false; // 写sqrt()函数调用太多拖慢时间，写i*i<a可能会溢出 当a是2时，2 <= 1因此不会进入循环 for(int i = 2; i <= a/i; i ++) { if(a % i == 0) return false; } return true;} 分解质因数12345678910111213141516171819int n;void divide(int n){ // 由于一个数有且只有一个大于sqrt(n)的质因子，故i枚举到sqrt(n)即可，大于根号n的质因子进行特判。 for(int i = 2; i <= n/i; i ++) if(n % i == 0) // 满足这个条件的话，i一定为质数，合数会被i的倍数筛除 ...