第一阶段考核 求解最大质数因子是多少的问题

方大侠

2. 编写一个程序，求解 600851475143 的最大质数因子是多少？pF]h:"c)

每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。r ?>^L

比如 13195 的质数因子有 5, 7, 13 和 29。

为什么我的代码哪里有问题，跑起来没有结果的，求大神解答；

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. #define BIG 600851475143
   
5. 
   
6. int main(){
   
7.         long long i,j,temp;
   
8.         _Bool sign=1;               //判断是否为素数，1为是
   
9.         long long num=BIG/2;
   
10. 
    
11.         for(i=9;i<num;i++){                             //BIG的公因数
    
12. 
    
13.                 for(j=2;j<=sqrt((double)i);j++){      //判断BIG的公因数 i 是否为质数   
    
14.                         if(i%j ==0){                          
    
15.                                 sign=0;
    
16.                                 break;                           //能整除（不为素数），sign=0，则跳出
    
17.                         }
    
18.                 }
    
19. 
    
20.                 if(sign){                                        //公因数 i 为素数，判断BIG能否整除
    
21.                         if(BIG%i ==0){
    
22.                                 temp =i;                      //最后赋值给temp
    
23.                                 num = BIG/i;
    
24.                         }
    
25.                 }
    
26.                 else{
    
27.                         sign=1;
    
28.                 }
    
29.         }
    
30.         printf("最大的素数是：%lld\n",temp);
    
31. return 0;
    
32. }
    

复制代码

jackz007

1. include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. #define BIG 600851475143
   
5. 
   
6. int main()
   
7. {
   
8.         long long b , c , d , i , j , r                          ;
   
9.         bool f                                                   ;
   
10.         d = (long long)(sqrt(BIG) + 1)                           ; // 确定循环上限
    
11.         for(i = d ; i > 1 ; i --) {                                // 输出所有可以整除 BIG 的因数
    
12.                 r = (long long)(BIG % i)                         ; // BIG 对 i 取余
    
13.                 if(! r) printf("%lld\n" , i)                     ; // r = 0 代表 BIG 可以被 i 整除  
    
14.         }
    
15.         for(i = d ; i > 1 ; i --) {                                // 在所有可以整除 BIG 的因数中挑选最大的质数
    
16.                 r = (long long)(BIG % i)                         ; // BIG 对 i 取余
    
17.                 if(! r) {                                          // r = 0 代表 BIG 可以被 i 整除
    
18.                         f = true                                 ; // 初始化素数标志为真
    
19.                         b = (long long)(sqrt(i) + 1)             ; // 确定循环上限
    
20.                         for(j = 2 ; j < b ; j ++) {                // 循环判定 i 是否为素数
    
21.                                 c = (long long)(i % j)           ;                                 
    
22.                                 if(! c) {                          // c = 0 代表 i 可以被 j 整除
    
23.                                         f = false                ; // 置素数标志为假
    
24.                                         break                    ;
    
25.                                 }
    
26.                         }         
    
27.                         if(f) {                                    // 如果 i 是素数
    
28.                                 printf("最大素数是：%lld\n" , i) ;
    
29.                                 break                            ;
    
30.                         }
    
31.                 }
    
32.         }
    
33. }
    

复制代码

    运行实况：
F:\[2019]\00.00.Exercise\C\longlong>x
486847
104441
59569
6857
1471
839
71
最大质数是：6857

F:\[2019]\00.00.Exercise\C\longlong>

方大侠

jackz007 发表于 2019-3-9 16:27
运行实况：
F:\[2019]\00.00.Exercise\C\longlong>x
486847

你好 因为是初学者，你写的有点看不懂。。。我主要想问一下我写的哪里错了，查不出结果，心累呀

82457097

楼主好像没有求big的公因数吧 只是遍历9-nun/2

jackz007

方大侠 发表于 2019-3-9 16:47
你好 因为是初学者，你写的有点看不懂。。。我主要想问一下我写的哪里错了，查不出结果，心累呀

     又按你的思路修改了程序，代码如下：

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. #define BIG 600851475143
   
5. 
   
6. int main()
   
7. {
   
8.         long long b , i , j , temp , num           ;
   
9.         _Bool sign                                 ; // 判断是否为素数，1为是
   
10. 
    
11.         num = (long long)sqrt(BIG) + 1             ; // 确定循环上限
    
12.         for(i = 9 ; i < num ; i ++) {                // BIG的公因数
    
13.                 if (BIG % i == 0) {                  // 如果 i 是 BIG 的公因数
    
14.                         sign = 1                   ; // 初始化标志，i 为素数
    
15.                         b = (long long)sqrt(i) + 1 ; // 确定循环上限
    
16.                         for(j = 2 ; j < b ; j ++) {  // 判断BIG的公因数 i 是否为素数   
    
17.                                 if(i % j == 0) {                          
    
18.                                         sign = 0   ;
    
19.                                         break      ; // 能整除（不为素数），sign = 0 ，则跳出
    
20.                                 }
    
21.                         }
    
22.                         if (sign) temp = i         ; // 因数 i 为素数
    
23.                 }
    
24.         }
    
25.         printf("最大的素数是：%lld\n" , temp)        ;
    
26. }
    

复制代码

        程序运行后长时间没反应原因是循环次数太多，关键修改是两处对 num 的赋值，第 1 处修改，第 2 处删除。

1. . . . . . .
   
2.         long long num=BIG/2;                  // 此句改为 num = (long long)sqrt(BIG) + 1 ;
   
3. . . . . . .
   
4.                                 num = BIG/i;  // 此句删除
   
5. . . . . . .

复制代码

萌笨笨萌