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

方大侠

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

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

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

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

#include<stdio.h>
#include<math.h>

#define BIG 600851475143

int main(){
        long long i,j,temp;
        _Bool sign=1;               //判断是否为素数，1为是
        long long num=BIG/2;

        for(i=9;i<num;i++){                             //BIG的公因数

                for(j=2;j<=sqrt((double)i);j++){      //判断BIG的公因数 i 是否为质数    
                        if(i%j ==0){                          
                                sign=0;
                                break;                           //能整除（不为素数），sign=0，则跳出
                        }
                }

                if(sign){                                        //公因数 i 为素数，判断BIG能否整除
                        if(BIG%i ==0){
                                temp =i;                      //最后赋值给temp
                                num = BIG/i;
                        }
                }
                else{
                        sign=1;
                }
        }
        printf("最大的素数是：%lld\n",temp);
return 0;
}

jackz007

include <stdio.h>
#include <math.h>

#define BIG 600851475143

int main()
{
        long long b , c , d , i , j , r                          ;
        bool f                                                   ;
        d = (long long)(sqrt(BIG) + 1)                           ; // 确定循环上限
        for(i = d ; i > 1 ; i --) {                                // 输出所有可以整除 BIG 的因数
                r = (long long)(BIG % i)                         ; // BIG 对 i 取余
                if(! r) printf("%lld\n" , i)                     ; // r = 0 代表 BIG 可以被 i 整除  
        }
        for(i = d ; i > 1 ; i --) {                                // 在所有可以整除 BIG 的因数中挑选最大的质数
                r = (long long)(BIG % i)                         ; // BIG 对 i 取余
                if(! r) {                                          // r = 0 代表 BIG 可以被 i 整除
                        f = true                                 ; // 初始化素数标志为真
                        b = (long long)(sqrt(i) + 1)             ; // 确定循环上限
                        for(j = 2 ; j < b ; j ++) {                // 循环判定 i 是否为素数 
                                c = (long long)(i % j)           ;                                 
                                if(! c) {                          // c = 0 代表 i 可以被 j 整除
                                        f = false                ; // 置素数标志为假
                                        break                    ;
                                }
                        }         
                        if(f) {                                    // 如果 i 是素数
                                printf("最大素数是：%lld\n" , i) ;
                                break                            ;
                        }
                }
        }
}

    运行实况：
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
你好 因为是初学者，你写的有点看不懂。。。我主要想问一下我写的哪里错了，查不出结果，心累呀

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

#include<stdio.h>
#include<math.h>

#define BIG 600851475143

int main()
{
        long long b , i , j , temp , num           ;
        _Bool sign                                 ; // 判断是否为素数，1为是

        num = (long long)sqrt(BIG) + 1             ; // 确定循环上限
        for(i = 9 ; i < num ; i ++) {                // BIG的公因数
                if (BIG % i == 0) {                  // 如果 i 是 BIG 的公因数
                        sign = 1                   ; // 初始化标志，i 为素数
                        b = (long long)sqrt(i) + 1 ; // 确定循环上限
                        for(j = 2 ; j < b ; j ++) {  // 判断BIG的公因数 i 是否为素数    
                                if(i % j == 0) {                          
                                        sign = 0   ;
                                        break      ; // 能整除（不为素数），sign = 0 ，则跳出
                                }
                        }
                        if (sign) temp = i         ; // 因数 i 为素数
                }
        }
        printf("最大的素数是：%lld\n" , temp)        ;
}

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

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

萌笨笨萌