[已解决]求助，质因数问题！！

灯火阑珊201

给出一个正整数n，请问它的最大质因数是多少？

我的代码如下：
#include<stdio.h>
int main()
{
    int n,i,x,y,f[100],j=0;
    _Bool flag=1;
    for(i=n/2;i;i--)
    {
        if(!(n%i))
        {
            for(x=2;x<i;x++)
            {
                if(i%x==0)
                {
                    flag=0;
                }
            }
        }
        if(flag)
        {
            printf("%d",i);
        }
    }
    return 0;
   
}

不知道哪错了。。求大佬指正！！

最佳答案

月排行榜 / 总排行榜

jackz007

2022-10-11 10:33:57

#include<stdio.h>
int main()
{
    int n,i,x,y,f[100] , j=0 ;
    int flag                 ;       // 用 int 就可以，免得麻烦
    scanf("%d" , & n)        ;
    for(i = n / 2 ; i ; i --) {
        if(! (n % i)) {
            flag = 1         ;       // 对于每一个 i 都需要事先假设其为素数
            for(x = 2 ; x < i ; x ++) {
                if(i % x == 0) {
                    flag = 0 ; 
                    break    ;       // 确定 i 不是素数后，没有必要继续循环
                }
            }
            if(flag) {
                printf("%d\n" , i) ;
                break              ; // 最大素数已经找到，也无需继续循环了
            }
        }
    }
}

        这是我写的

#include<stdio.h>

int main(void)
{
        int i , k , n                ;
        scanf("%d" , & n)            ;
        for(i = 2 , k = n ; i * i < k + 1 ;) {
                if(! (k % i)) k /= i ;
                else i ++            ;
        }
        printf("%d\n" , k)           ;
}

        递归函数版

#include<stdio.h>

int foo(const int n)
{
        int i , r                         ;
        for(i = n / 2 ; i > 1 ; i --) {
                if(! (n % i)) {
                        r = foo(i)        ;
                        break             ;
                }
        }
        return (i == 1) ? n : r           ;
}

int main(void)
{
        int n                             ;
        scanf("%d" , & n)                 ;
        printf("%d\n" , foo(n))           ;
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
1234567
9721

D:\[00.Exerciese.2022]\C>

跳转到最佳答案楼层

homeskating

没导boolean的头文件吗？

homeskating

homeskating 发表于 2022-10-11 10:27
没导boolean的头文件吗？

头文件是<stdbool.h>

jackz007

#include<stdio.h>
int main()
{
    int n,i,x,y,f[100] , j=0 ;
    int flag                 ;       // 用 int 就可以，免得麻烦
    scanf("%d" , & n)        ;
    for(i = n / 2 ; i ; i --) {
        if(! (n % i)) {
            flag = 1         ;       // 对于每一个 i 都需要事先假设其为素数
            for(x = 2 ; x < i ; x ++) {
                if(i % x == 0) {
                    flag = 0 ; 
                    break    ;       // 确定 i 不是素数后，没有必要继续循环
                }
            }
            if(flag) {
                printf("%d\n" , i) ;
                break              ; // 最大素数已经找到，也无需继续循环了
            }
        }
    }
}

        这是我写的

#include<stdio.h>

int main(void)
{
        int i , k , n                ;
        scanf("%d" , & n)            ;
        for(i = 2 , k = n ; i * i < k + 1 ;) {
                if(! (k % i)) k /= i ;
                else i ++            ;
        }
        printf("%d\n" , k)           ;
}

        递归函数版

#include<stdio.h>

int foo(const int n)
{
        int i , r                         ;
        for(i = n / 2 ; i > 1 ; i --) {
                if(! (n % i)) {
                        r = foo(i)        ;
                        break             ;
                }
        }
        return (i == 1) ? n : r           ;
}

int main(void)
{
        int n                             ;
        scanf("%d" , & n)                 ;
        printf("%d\n" , foo(n))           ;
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
1234567
9721

D:\[00.Exerciese.2022]\C>

灯火阑珊201

jackz007 发表于 2022-10-11 10:33
这是我写的

        递归函数版

感谢大佬！！！

灯火阑珊201

jackz007 发表于 2022-10-11 10:33
这是我写的

        递归函数版

我想问一下
if(! (k % i)) k /= i ;
这一行代码是干啥的，，我看了半天没看懂。。。

jackz007

灯火阑珊201 发表于 2022-10-11 23:27
我想问一下
if(! (k % i)) k /= i ;
这一行代码是干啥的，，我看了半天没看懂。。。

        k 一开始等于 n，i 从 2 开始，由小到大循环枚举 k 的因子，找到后，及时从 k 中进行剔除，k /= i 就是在进行剔除操作。等到循环结束的时候，k 自然就是一个素数了，而且，还是最大的那一个。

灯火阑珊201

jackz007 发表于 2022-10-11 23:32
k 一开始等于 n，i 从 2 开始，由小到大循环枚举 k 的因子，找到后，及时从 k 中进行剔除，k / ...

感谢感谢！！！懂了