資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C語言程式：查詢數字的最大質因數？
在本節中，我們將學習如何高效地找到一個數字的最大質因數。假設有一個數字n = 1092，我們需要找到它的最大質因數。1092的質因數是2, 2, 3, 7, 13。因此，最大質因數是13。為了解決這個問題，我們必須遵循以下規則：
當數字能被2整除時，將2儲存為最大質因數，並重復將數字除以2。
現在數字一定是奇數。從3開始到數字的平方根，如果數字能被當前值整除，則將該因數儲存為最大質因數，並將數字除以當前值，然後繼續。
最後，如果數字大於2（即不為1），則得到最大質因數。
讓我們看看演算法來更好地理解。
演算法
getMaxPrimeFactors(n)
begin while n is divisible by 2, do max := 2 n := n / 2 done for i := 3 to √𝑛, increase i by 2, do while n is divisible by i, do max := i n := n / i done done if n > 2, then max := n end if end
示例
#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
int i, max = -1;
while(n % 2 == 0) {
max = 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) {
max = i;
n = n/i;
}
}
if(n > 2) {
max = n;
}
return max;
}
main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
printf("Max prime factor: %d", getMaxPrimeFactor(n));
}輸出
Enter a number: 24024 Max prime factor: 13
更新於：2019年7月30日
2K+ 次瀏覽
廣告