数论——分解质因数
记录一道关于数论的题目，题目本身不难，主要是学习一下思想~
思路
根据算术基本定理又称唯─分解定理，对于任何一个合数，我们都可以用几个质数的幂的乘积来表示。
如:
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);
}
}
总结
初学数论，多积累思想和经验很重要！
文章粗浅，希望对大家有帮助！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/159829.html
