质数

试除法定质数

bool is_prime(int num)
{if(num < 2)return false;for(int i = 2; i <= num / i; ++i)if(num % i == 0)return false;return true;
}

分解质因数

	// 一个数最小的因数就是质因数int n, num;cin >> n;for(int j = 0; j < n; ++j){cin >> num;for(int i = 2; i <= num / i; ++i){if(num % i == 0){int cnt = 0;while(num % i == 0){num /= i;cnt++;}cout << i << " " << cnt << endl;}}if(num  > 1)cout << num << " " << 1 << endl;cout << endl;}

筛质数

void get_prime()
{for(int i = 2; i <= n; ++i){if(visited[i] == false)primes[idx++] = i;  // 埃式筛法for(int j = i + i; j <= n; j += i)visited[j] = true;}
}

约数

试除法求约数

int main()
{cin >> n;for(int i = 0; i < n; ++i){cin >> num;vector<int> ret;            // 包含1和num本身for(int j = 1; j <= num / j; ++j){if(num % j == 0){ret.push_back(j);   // 这里可同时获得两个约数if(j != num / j)ret.push_back(num / j);}}sort(ret.begin(), ret.end());for(auto a : ret)cout << a << " ";cout << endl;}return 0;
}

乘积的约数个数

const int mod = 1e9 + 7;
int main()
{cin >> n;for(int i = 0; i < n; ++i){cin >> num;for(int j = 2; j <= num / j; ++j){               // 试除法求质因数及其指数while(num % j == 0){num /= j;all[j]++;}}if(num != 1)    // num本身是一个大的质因数all[num]++;}long long ret = 1;for(auto &a : all)  // 乘积总约数个数：质因数指数+1的乘积ret = ret * (a.second + 1) % mod;cout << ret;return 0;
}

最大公约数

int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}

欧拉函数

int main()
{int n;cin >> n;while(n--){int num;cin >> num;int ret = num;for(int i = 2; i <= num / i; ++i){if(num % i == 0){               // 注意运算顺序ret = ret / i * (i - 1) ;while(num % i == 0)num /= i;}}if(num > 1)ret = ret / num * (num - 1) ;cout << ret << endl;}return 0;
}

筛法求欧拉函数和

void get_phi(int n)
{phi[1] = 1;for(int i = 2; i <= n; ++i){if(visited[i] == false){primes[idx++] = i;              // 获取质数phi[i] = i - 1;                 // 质数的欧拉函数}for(int j = 0; primes[j] <= n / i; ++j){visited[primes[j] * i] = true;  // 标记非质数if(i % primes[j] == 0){                               // p[j]为i的质因数phi[primes[j] * i] = phi[i] * primes[j];break;}else                            // p[j]不为i的质因数，要另乘一个p[j]质因数项phi[primes[j] * i] = phi[i] * primes[j] / primes[j] * (primes[j] - 1);}}
}