数据结构
网络
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+ 次浏览
广告