能夠高效列印給定數字的所有質因子的 C 語言程式?
本節中,我們將瞭解如何高效地獲取某個數字的所有素因數。例如數字 n = 1092,我們需要獲取其所有素因數。1092 的素因數為 2、2、3、7、13。要解決這個問題,我們必須遵循以下規則:
如果這個數字能被 2 整除,則列印 2,並將這個數字反覆除以 2。
現在這個數字肯定為奇數。現在從 3 到這個數字的平方根,如果數字能被當前的值整除,則列印,然後用當前數字除以這個數字來改變這個數字,然後繼續。
讓我們看一看演算法以獲得更好的思路。
演算法
printPrimeFactors(n)
begin while n is divisible by 2, do print 2 n := n / 2 done for i := 3 to √𝑛, increase i by 2, do while n is divisible by i, do print i n := n / i done done if n > 2, then print n end if end
示例
#include<stdio.h> #include<math.h> void primeFactors(int n) { int i; while(n % 2 == 0) { printf("%d, ", 2); n = n/2; //reduce n by dividing this by 2 } for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers while(n % i == 0) { printf("%d, ", i); n = n/i; } } if(n > 2) { printf("%d, ", n); } } main() { int n; printf("Enter a number: "); scanf("%d", &n); primeFactors(n); }
輸出
Enter a number: 24024 2, 2, 2, 3, 7, 11, 13,
廣告