第一阶段考核 求解最大质数因子是多少的问题
本帖最后由 方大侠 于 2019-3-9 16:45 编辑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 于 2019-3-9 16:35 编辑
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:\\00.00.Exercise\C\longlong>x
486847
104441
59569
6857
1471
839
71
最大质数是：6857
F:\\00.00.Exercise\C\longlong> jackz007 发表于 2019-3-9 16:27
运行实况：
F:\\00.00.Exercise\C\longlong>x
486847
你好 因为是初学者，你写的有点看不懂。。。我主要想问一下我写的哪里错了，查不出结果，心累呀 楼主好像没有求big的公因数吧 只是遍历9-nun/2 本帖最后由 jackz007 于 2019-3-10 11:51 编辑
方大侠 发表于 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;// 此句删除
. . . . . . {:5_106:}
页:
[1]