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

风眠

速度很慢，求更优解

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

学习学习

奋斗中的鱼

超神奇葩天才

1. import math
   
2. import math
   
3. global n
   
4. global factor
   
5. factor = []
   
6. n = int(input())
   
7. #n = 600851475143
   
8. 
   
9. def _factor():
   
10.     global n
    
11.     n = int(n)
    
12.     for i in range(2,math.isqrt(n)+3):
    
13.         if n % i == 0:
    
14.             n /= i
    
15.             factor.append(i)
    
16.             _factor()
    
17.         elif n <= i:
    
18.             break
    
19. 
    
20. _factor()
    
21. print(factor[-1])
    

复制代码

这个思路怎么样

salt_eto

直接枚举，
这题因为因数数量多，欧拉筛效率反而不如穷举

1. ulong test3(ulong n)
   
2. {
   
3.   ulong res=2;
   
4.   while(res*res<n)
   
5.   {
   
6.     if(n%res)
   
7.     {
   
8.       res++;
   
9.       continue;
   
10.     }
    
11.     n/=res;
    
12.   }
    
13.   return std::max(res,n);
    
14. }

复制代码

1433391058

test

hejiage

原来全部是数学问题的编程解法

假妖怪

真不错