資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C語言程式：如何求一個數的所有奇數因子的和？
在本節中，我們將學習如何高效地求出一個數的所有奇數質因子的和。例如，給定一個數 n = 1092，我們需要求出它的所有因子。1092 的質因子為 2、2、3、7、13。所有奇數因子的和為 3 + 7 + 13 = 23。為了解決這個問題，我們需要遵循以下規則：
如果一個數能被 2 整除，則忽略該因子，並重復除以 2。
現在這個數一定是奇數。從 3 開始，一直到該數的平方根，如果該數能被當前值整除，則將該因子加到總和中，並將該數除以當前值，然後繼續。
最後，如果剩下的數是奇數，則也將它加到總和中。
讓我們看看演算法來更好地理解。
演算法
printPrimeFactors(n)
begin sum := 0 while n is divisible by 2, do n := n / 2 done for i := 3 to √𝑛, increase i by 2, do while n is divisible by i, do sum := sum + i n := n / i done done if n > 2, then if n is odd, then sum := sum + n end if end if end
示例
#include<stdio.h>
#include<math.h>
int sumOddFactors(int n) {
int i, sum = 0;
while(n % 2 == 0) {
n = n/2; //reduce n by dividing this by 2
}
//as the number is not divisible by 2 anymore, all factors are odd
for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get
only odd numbers
while(n % i == 0) {
sum += i;
n = n/i;
}
}
if(n > 2) {
if(n%2 == 1)
sum += n;
}
return sum;
}
main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
printf("Sum of all odd prime factors: %d", sumOddFactors(n));
}輸出
Enter a number: 1092 Sum of all odd prime factors: 23
更新於: 2019年7月30日
1K+ 瀏覽量
廣告