洛谷:P1075:质因数分解


洛谷:P1075:质因数分解

Table of Contents

题目

P1075:质因数分解

分析

初看这道题应该要写一个判定一个数是否是质数的函数。但是,由于题目保证“正整数n是两个不同的质数的乘积”,也就是说这个数一定只能分解为两个质数的乘积。所以就简单了:不用判定质数,而只要从大到小找到这个数的第一个因子,就是答案。

答案

Solution

思考

这道题虽然简单,但还是包含了数论(特别是质数)的重要理论。你看得出来吗?

11行的循环终点到sqrt(n)为止就是。一个合数如果是两个质数的乘积(\(p\times q\)),那么一定有一个质因子小于等于\(\sqrt n\),而另一个大于等于\(\sqrt n\)。用这个循环进行计算,可以保证先找到小的那个质因子(i),然后用n/i就能找到大的那个。

上一篇 下一篇