数论——分解质因数
记录一道关于数论的题目，题目本身不难，主要是学习一下思想~
思路
根据算术基本定理又称唯─分解定理，对于任何一个合数，我们都可以用几个质数的幂的乘积来表示。
如:
12 = 2^2 * 3
20 = 2^2 * 5
30 = 2 * 3 * 5
接下来我们利用这个公式分解质因数。
设一个质数为p,如果 n % p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n / p , 这样就从n中剔除了一个p,接着重复上述两步，直到 n % p != 0
代码
/**
* 注意：以上代码中for循环的结束条件也是i <= n / i，因为根据公式，最多只可能有一个质因数是大于 根号n,
* 因为有两个的话，乘积肯定超过n了。所以当for循环结束后判断n是否大于1，如果大于就说明有一个大于 根号n 的质因数。
*/
public class Main { public static void prime(int n) { for (int i = 2; i <= n / i; i++) {//即i*i<=n int a = 0, b = 0; while (n % i == 0) { a = i; n /= i; b++; } if (b > 0) System.out.println("质因数之一： " + a + " 的 " + b + " 次方"); } if (n > 1) System.out.println("有一个大于根号n 的质因数:" + n); } public static void main(String[] args) { prime(30); } }
总结
初学数论，多积累思想和经验很重要！
文章粗浅，希望对大家有帮助！
