质数
- 大于1的整数中，如果只包含1和它本身这两个约数，就被称为质数，也叫素数
质数的判定
- 试除法---时间复杂度O（sqrt（n））
bool isprime(int x){
if(x < 2) return 0;
for(int i=2;i <= x/i;i++){
if(x%i==0)
return false;
}
return true;
}
分解质因数
- 试除法---时间复杂度O（sqrt（n））
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ‘ ‘ << s << endl;
}
if (x > 1) cout << x << ‘ ‘ << 1 << endl;
cout << endl;
}