质因数分解，各位码农们讲一下吧。

Question

这个题目该怎么做鸭，能不能讲一下思路，代码。看了半天没看懂，不知道如何表达最大的质数。

Answer 1

思路，从最大的质因数找起

#include <stdio.h>
int isp(int n)
{
if (n < 2) return 0;
for (int i = 2; i < n; i++)
if (n % i == 0) return 0;
return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = n - 1; i >=1; i--)
    {
        if (n % i == 0 && isp(i)) { printf("%d", i); return 0; }
    }
    return 0;
}

也可以这么写

#include <stdio.h>

int main()
{
    int n, i, j, maxPrime = 0;
    printf("请输入一个正整数n：");
    scanf("%d", &n);

    for(i = 2; i <= n; i++){
        if(n % i == 0){
            maxPrime = i; // 先记录当前的i，可能是最大的质因数
            while(n % i == 0){
                n /= i;
            }
        }
    }

    if(maxPrime != 0){
        printf("最大的质因数是：%d\n", maxPrime);
    }
    else{
        printf("%d没有质因数\n", n);
    }

    return 0;
}