文章目录
什么是质数、合数判断质数分解质因数什么是质数、合数
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数,质数也叫素数。
与质数相对的是合数,合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数整除的数。
判断质数
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;}
循环中不建议写成i<=sqrt(n),因为sqrt函数很慢,每次for循环都会执行一遍,耗时。
也不要写成i*i<=n,会存在溢出风险。
时间复杂度:O(sqrt(n))
分解质因数
把一个合数分解成若干个质因数的乘积的形式,即求质因数的过程叫做分解质因数。
如:12=2 * 2 * 3
void divide(int n){for(int i=2; i<=n/i; i++)if(n%i == 0){int s=0;while(n%i == 0){n/=i;s++;}cout<<i<<" "<<s; //s是i的次方数}if(n>1) cout<<n<<" "<<1; //此时n是大于根号n的那个质因子}
时间复杂度:O(sqrt(n))(最坏情况下)
为什么这里也只用循环到n/i就行了呢?
因为,n的质因子最多只有一个大于sqrt(n)的(很好证明,因为如果有两个的话相乘就大于n了,这是矛盾了),所以,我们只需要先找到小于sqrt(n)的质因子,循环结束后,n若是大于1的,说明此时这个n就是那个大于sqrt(n)的质因子。
我们可能会疑问,我们要找的是n的所有的质因子,可是你在循环内枚举时 i 是从2 ~ n/i的,这中间i可是包含的有合数的,会不会有问题呢?
其实,是没有问题的,因为当我们枚举到 i 时,就意味着我们已经把 n 的2~i-1的所有质因子都除干净了(n/=i),也就是说我们此时的n中不含有2 ~ i -1的任何质因子了,如果满足if(n%i == 0),那么说明 i 中也一定不含2 ~ i -1的任何质因子,那么这个 i 一定是个质数。