数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法学研究在 C++ 中打印所有质因数及其指数
在该问题中，已给定一个数字 N，我们需要找到能整除该数字的所有唯一质因数及其指数。
让我们举一个例子来理解该主题——
Input: 55 Output: 5 power 1 11 power 1
解释——
55 可以被 5 和 11 整除。
要解决此问题，一种简单的方法就是找到 N 的质因数。然后找到能整除数字 N 的质数的指数并打印它。
算法
有效的方法
Step 1: Find an array s[N+1]. s[i] = prime factor of i dividing N. Step 2: Find all powers of i. prime = s[N] and pow = 1. Step 3: While (N > 1) : Step 3.1: N /= s[N]; Step 3.2: if(prime = s[N]) : pow++ Step 4: print prime and pow.
示例
#include<bits/stdc++.h>
using namespace std;
void primes(int N, int s[]){
vector <bool> prime(N+1, false);
for (int i=2; i<=N; i+=2)
s[i] = 2;
for (int i=3; i<=N; i+=2){
if (prime[i] == false){
s[i] = i;
for (int j=i; j*i<=N; j+=2){
if (prime[i*j] == false){
prime[i*j] = true;
s[i*j] = i;
}
}
}
}
}
void generatePrimeFactors(int N) {
int s[N+1];
primes(N, s);
cout<<"Factor\tPower"<<endl;
int prime = s[N];
int power = 1;
while (N > 1){
N /= s[N];
if (prime == s[N]){
power++;
continue;
}
cout<<prime<<"\t"<<power<<endl;
prime = s[N];
power = 1;
}
}
int main() {
int N = 55;
cout<<"The prime factors are and their powers are :\n";
generatePrimeFactors(N);
return 0;
}输出
质数为，其指数为——
Factor Power 5 1 11 1
更新时间：17-Jan-2020
591 次浏览
广告