数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装研究
法律研究C++ 中一个大数的质数因子
在这个问题中，我们给定一个整数 N <= 10^18。我们的任务是打印该数的所有质因数及其出现的频率。
我们举个例子来理解问题：
Input: 100 Output: 2 2 5 2 Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.
要解决这个问题，我们必须找到这个数的质因数，然后计算它们的频率。
为此，我们将检查 2 作为因子的频率，然后用 2 除以该数。然后，从 3 到平方根 n 检查。除以每个作为该数因子的质数并增加其频率。如果该数变为 1 则停止。然后打印所有质数及其频率。
以下代码显示了我们解决方案的实现：
示例
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
}输出
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1
更新于： 2020 年 2 月 3 日
926 次浏览
广告