【蓝桥备赛】质因数个数——数论

本文主要是介绍【蓝桥备赛】质因数个数——数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

质因数个数

个人思路

根据算术基本定理，每个大于1的数都可以写成若干质数相乘的形式。因此，我们从小到大依次求出这个数可能存在的质因数。

参考代码

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long res = 0;long limit = (long) Math.sqrt(n);for (long i = 2; i < limit; ++i) {long cnt = 0;while (n % i == 0) {// 当前i一定是一个质数，因为比他小的因数都已经被分解成其他更小的质数了++cnt;n /= i;}if (cnt > 0) ++res;}if (n > 1) ++res; // 剩下最后一个因子也是质数System.out.println(res);}
}

C/C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int main()
{ll n, res = 0;cin >> n;ll count = sqrt(n);for (ll i = 2; i < count; ++i){ll cnt = 0;while(n % i == 0){	// 当前i一定是一个质数，因为比他小的因数都已经被分解成其他更小的质数了++cnt;n /= i;}if(cnt > 0) ++res;}if(n > 1) ++res; // 剩下最后一个因子也是质数cout << res;return 0;
}

这篇关于【蓝桥备赛】质因数个数——数论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---