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

灯火阑珊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

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

复制代码

        这是我写的

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int i , k , n                ;
   
6.         scanf("%d" , & n)            ;
   
7.         for(i = 2 , k = n ; i * i < k + 1 ;) {
   
8.                 if(! (k % i)) k /= i ;
   
9.                 else i ++            ;
   
10.         }
    
11.         printf("%d\n" , k)           ;
    
12. }

复制代码

        递归函数版

1. #include<stdio.h>
   
2. 
   
3. int foo(const int n)
   
4. {
   
5.         int i , r                         ;
   
6.         for(i = n / 2 ; i > 1 ; i --) {
   
7.                 if(! (n % i)) {
   
8.                         r = foo(i)        ;
   
9.                         break             ;
   
10.                 }
    
11.         }
    
12.         return (i == 1) ? n : r           ;
    
13. }
    
14. 
    
15. int main(void)
    
16. {
    
17.         int n                             ;
    
18.         scanf("%d" , & n)                 ;
    
19.         printf("%d\n" , foo(n))           ;
    
20. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 1234567
   
5. 9721
   
6. 
   
7. D:\[00.Exerciese.2022]\C>

复制代码

跳转到最佳答案楼层

homeskating

没导boolean的头文件吗？

homeskating

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

头文件是<stdbool.h>

jackz007

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

复制代码

        这是我写的

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int i , k , n                ;
   
6.         scanf("%d" , & n)            ;
   
7.         for(i = 2 , k = n ; i * i < k + 1 ;) {
   
8.                 if(! (k % i)) k /= i ;
   
9.                 else i ++            ;
   
10.         }
    
11.         printf("%d\n" , k)           ;
    
12. }

复制代码

        递归函数版

1. #include<stdio.h>
   
2. 
   
3. int foo(const int n)
   
4. {
   
5.         int i , r                         ;
   
6.         for(i = n / 2 ; i > 1 ; i --) {
   
7.                 if(! (n % i)) {
   
8.                         r = foo(i)        ;
   
9.                         break             ;
   
10.                 }
    
11.         }
    
12.         return (i == 1) ? n : r           ;
    
13. }
    
14. 
    
15. int main(void)
    
16. {
    
17.         int n                             ;
    
18.         scanf("%d" , & n)                 ;
    
19.         printf("%d\n" , foo(n))           ;
    
20. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 1234567
   
5. 9721
   
6. 
   
7. 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 / ...

感谢感谢！！！懂了