数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C/C++程序：求解一个数的唯一素因数的乘积？
在本节中，我们将学习如何高效地计算一个数的唯一素因数的乘积。例如，数字n = 1092，我们需要求其唯一素因数的乘积。1092的素因数是2, 2, 3, 7, 13。因此，唯一的素因数是{2, 3, 7, 13}，它们的乘积是546。为了解决这个问题，我们需要遵循以下规则：
当数字能被2整除时，将2乘以乘积，然后反复将数字除以2，后续的2将被忽略。
现在数字一定是奇数。从3开始到数字的平方根，如果数字能被当前值整除，则将该因数乘以乘积，并将数字除以当前值，然后继续。后续的相同因数将被忽略。
最后，如果数字大于2（即不为1），则将剩余的数字乘以乘积。
让我们看看算法来更好地理解。
算法
uniquePrimeProduct(n)
begin prod := 1 if n is divisible by 2, then prod := prod * 2 n := n / 2 end if while n is divisible by 2, do n := n / 2 done for i := 3 to √𝑛, increase i by 2, do if n is divisible by i, then prod := prod * i n := n / i end if while n is divisible by i, do n := n / i done done if n > 2, then prod := prod * n end if end
示例
#include<stdio.h>
#include<math.h>
int uniquePrimeProduct(int n){
int i, prod = 1;
if(n % 2 == 0){
prod *= 2;
n = n/2;
}
while(n % 2 == 0){//skip next 2s
n = n/2;
}
for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
if(n % i == 0){
prod *= i;
n = n/i;
}
while(n % i == 0){ //skip next i's
n = n/i;
}
}
if(n < 2){
prod *= n;
}
return prod;
}
main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
printf("Product of prime factors: %d", uniquePrimeProduct(n));
}输出
Enter a number: 1092 Product of prime factors: 546
更新于：2019年7月30日
540 次浏览
广告