编写一个程序，求解 600851475143 的最大质数因子是多少

ksksasd

#include <stdio.h>
int main()
{
       long long a;int flag=0;
       for(a=600851475142;a<600851475143;a--) //最大质数就是取余为0
       {
               if(600851475143%a==0)
               {
                       printf("%lld",a);
                       flag=1;
            }
                if(flag)     //找到了最大质数，flag就=1
                  break;    //跳出for循环
           }
          
        return 0;
}

wp231957

这样做  ，首先你找不到最大质数，另外，就是循环次数太多了  

1. s=600851475143
   
2. a=[]
   
3. def iss(n):
   
4.     if n==1:return 0
   
5.     for x in range(2,n):
   
6.         if n%x==0:
   
7.             return 0
   
8.     return 1            
   
9. 
   
10. for x in range(1,10001):
    
11.     if iss(x):a.append(x)
    
12. 
    
13. print(s,"=",end="")
    
14. for y in a:
    
15.     if s%y==0:
    
16.         s//=y
    
17.         if s==1:
    
18.             print(y)
    
19.         else:
    
20.             print(y,"*",end="")     
    
21. '''
    
22. PS C:\Users\Administrator> & C:/Programs/Python/python.exe d:/wp/test7.py
    
23. 600851475143 =71 *839 *1471 *6857
    
24. '''

复制代码

wp231957

探测该数的所有因数：

1. s=s1=600851475143
   
2. a=[]
   
3. def iss(n):
   
4.     if n==1:return 0
   
5.     for x in range(2,n):
   
6.         if n%x==0:
   
7.             return 0
   
8.     return 1            
   
9. 
   
10. for x in range(1,10001):
    
11.     if iss(x):a.append(x)
    
12. 
    
13. b=[]
    
14. for y in a:
    
15.     if s%y==0:
    
16.         s//=y
    
17.         b.append(y)
    
18. 
    
19. import itertools
    
20. m=[]
    
21. for x in range(1,len(b)+1):
    
22.     m.extend(list(itertools.combinations(b,x)))
    
23. xh=1
    
24. print("%2d: %12d = %d * %d"%(xh,s1,1,s1))
    
25. for x in m:
    
26.     t=1
    
27.     for y in x:
    
28.         t*=y
    
29.     xh+=1   
    
30.     print("%2d: %12d = %d * %d"%(xh,s1,t,s1//t))
    
31. 
    
32. '''
    
33. PS C:\Users\Administrator> & C:/Programs/Python/python.exe d:/wp/test7.py
    
34. 1: 600851475143 = 1 * 600851475143
    
35. 2: 600851475143 = 71 * 8462696833
    
36. 3: 600851475143 = 839 * 716151937
    
37. 4: 600851475143 = 1471 * 408464633
    
38. 5: 600851475143 = 6857 * 87625999
    
39. 6: 600851475143 = 59569 * 10086647
    
40. 7: 600851475143 = 104441 * 5753023
    
41. 8: 600851475143 = 486847 * 1234169
    
42. 9: 600851475143 = 1234169 * 486847
    
43. 10: 600851475143 = 5753023 * 104441
    
44. 11: 600851475143 = 10086647 * 59569
    
45. 12: 600851475143 = 87625999 * 6857
    
46. 13: 600851475143 = 408464633 * 1471
    
47. 14: 600851475143 = 716151937 * 839
    
48. 15: 600851475143 = 8462696833 * 71
    
49. 16: 600851475143 = 600851475143 * 1
    
50. PS C:\Users\Administrator>
    
51. '''   

复制代码

傻眼貓咪

答案是 6857 吗？

1. #include <stdio.h>
   
2. 
   
3. int isPrime(long long n) {
   
4.     if (n == 2 || n == 3) return 1;
   
5.     for (long long i = 2; i * i < n; i++) if (!(n % i)) return 0;
   
6.     return 1;
   
7. }
   
8. 
   
9. long long largestPrimeFactor(long long n) {
   
10.     long long prime = 2;
    
11.     while (n > 1) {
    
12.         while (n % prime == 0) n /= prime;
    
13.         if (n == 1) break;
    
14.         do {
    
15.             prime++;
    
16.         } while (!isPrime(prime));
    
17.     }
    
18.     return prime;
    
19. }
    
20. 
    
21. int main()
    
22. {
    
23.     printf("%lld", largestPrimeFactor(600851475143));
    
24.     return 0;
    
25. }

复制代码

1. 6857

复制代码

我的思路：
因为 600851475143 数字太大，不可能从 1 至 600851475143 测试是否为它的因数、质数两个测试，这样时间复杂度是不允许的。反方向思考，逐个找出小于 600851475143 的质数，然后再判断是否能除整，便是答案了

傻眼貓咪

Python

1. from math import sqrt
   
2. def isPrime(n):
   
3.     if(n in (2, 3)): return True
   
4.     for i in range(2, int(sqrt(n))):
   
5.         if not n%i: return False
   
6.     return True
   
7. 
   
8. def largestPrimeFactor(n):
   
9.     prime = 2
   
10.     while n > 1:
    
11.         while not n%prime: n /= prime
    
12.         if n == 1: break
    
13.         prime += 1
    
14.         while not isPrime(prime):
    
15.             prime += 1
    
16.     return prime
    
17. 
    
18. print(largestPrimeFactor(600851475143))

复制代码

ksksasd

wp231957 发表于 2022-1-30 09:08
这样做  ，首先你找不到最大质数，另外，就是循环次数太多了

不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取余为0吗？

ksksasd

ksksasd 发表于 2022-1-30 12:59
不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取 ...

就比如我把600851475143改成小一点的数就能计算出正确结果了

ksksasd

ksksasd 发表于 2022-1-30 13:10
就比如我把600851475143改成小一点的数就能计算出正确结果了

我理解了这样不能算出质数因子；
我搞错定义了；
但为什么我的返回值是空白？
不应该打印最大除数吗？

wp231957

ksksasd 发表于 2022-1-30 12:59
不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取 ...

18是质数吗，36的最大质因数就是3

ksksasd

wp231957 发表于 2022-1-30 13:23
18是质数吗，36的最大质因数就是3

谢谢你的回复！我搞错了质数定义了。
我的原代码中求的最大整除除数。返回值为空白。这个问题能帮我解决吗？

ksksasd

ksksasd 发表于 2022-1-30 14:51
谢谢你的回复！我搞错了质数定义了。
我的原代码中求的最大整除除数。返回值为空白。这个问题能帮我解决 ...

但我把数字改小，就能得出正确答案。
long long 定义也应该没问题的。

jhq999

1. int main()
   
2. {
   
3.         unsigned long long val=0,yinzi=2,s=1;
   
4.         printf("输入一个数字:");
   
5.         scanf_s("%llu",&val);
   
6. 
   
7.         getchar();
   
8.         for (int i = yinzi; i < val/yinzi ;i++)//任何一个数都可以分解成全部质数因子的积
   
9.         {
   
10.                 while(val%yinzi)//最小的因子一定是质数因子，最大的因子对应的一定是最小因子
    
11.                 {
    
12.                         yinzi++;
    
13.                 }
    
14.                 s*=yinzi;
    
15.                 printf("%llu×",yinzi);
    
16.                 val/=yinzi;
    
17.                 while(!(val%yinzi))
    
18.                 {
    
19.                     val/=yinzi;
    
20.                         s*=yinzi;
    
21.                         printf("%llu×",yinzi);
    
22.                 }
    
23.         }
    
24. 
    
25.         if(val>1)s*=val,printf("%llu=%llu",val,s);//质数因子的积
    
26.         else
    
27.                 printf("=%llu",s);
    
28.         printf("最大质数因子：%llu",val>yinzi?val:yinzi);
    
29.         return 0;
    
30. }

复制代码

例如：98
2×49=2×7×7=98

YSW9527

ksksasd 发表于 2022-1-30 14:52
但我把数字改小，就能得出正确答案。
long long 定义也应该没问题的。

数字太大了，计算机得跑一段时间

malloy_123

1. int func2(long long num){
   
2.         long long i=2;
   
3.         while(i!=num){
   
4.                 if(num%i==0)
   
5.                         num=num/i;
   
6.                 else{
   
7.                         i++;
   
8.                 }
   
9.         }
   
10.         return num;
    
11. }

复制代码

大概就是依次拆解掉最小的因子，最后得到的质数商就是要求的最大质数因子