题目3：找出一个合数的最大质数因子

Ian_Li

欧拉计划 发表于 2023-5-29 02:41
出师不捷啊，第三题就出纰漏了！

确实是漏了大的那个因数没有检测是否为质数，刚开始有鱼油指出时我竟 ...

加上检查大的因子是不是也不对呀?
如果n有两个大于Math.sqrt(n)的质数因子a,b;并且a<b
循环的过程中,会先t = b;
再t = a;
最后返回a

Ian_Li

还有最后的代码写的,for循环里的i也没用到呀.

1. import math
   
2. 
   
3. n = 600851475143
   
4. k = 2
   
5. 
   
6. for i in range(0, math.isqrt(n)):
   
7.     if k >= n:
   
8.         break
   
9.     elif n % k == 0:
   
10.         n = n // k
    
11.     else:
    
12.         k = k + 1
    
13.         
    
14. print(n)

复制代码

Ian_Li

1. public static void main(String[] args) {
   
2.         long res = getSum(600851475143l);
   
3.         System.out.println(res);
   
4.     }
   
5. 
   
6.     private static long getSum(long n) {
   
7.         long k = 2;
   
8.         while (k < n) {
   
9.             if (n % k == 0) {
   
10.                 n = n / k;
    
11.             } else {
    
12.                 k++;
    
13.             }
    
14.         }
    
15.         return n;
    
16.     }

复制代码

xw20010211

looklook

nkysp

好

风眠

速度很慢，求更优解

1. def chick(x):
   
2.     for i in range(2,x):
   
3.         if not x%i:
   
4.             return False
   
5.     else:
   
6.         return True
   
7. 
   
8. 
   
9. a=600851475143
   
10. for i in range(a//2,0,-1):
    
11.     if not a%i:
    
12.         if chick(i):
    
13.             print(i)
    
14.             break
    

复制代码

name_Liu

1

依瓦尼格

学习中

zhangjinxuan

欧拉计划 发表于 2023-5-31 01:27
刺激啊，复杂度已经降到 O(√n)

Pollard-Rho 呢

左右丶

讲得很详细，学到了

chenxyong

打卡打卡

AtoposK

学会了

AtoposK

讲得很好

141319

1

141319

1

这是豆豆啊

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

number = 600851475143
result = largest_prime_factor(number)

print(result)

居仔爸爸

小粪坨屎团团小兔球球

lU553178681

学些学习！

sharp46

学习学习

奋斗中的鱼