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

超神奇葩天才

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

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

假妖怪

真不错

1Asdusdhjssd

学习

gametsbug

学习

xiaot1014

1. if __name__ == '__main__':
   
2.     goal = 600851475143
   
3.     i = 2
   
4.     while goal > i:
   
5.         if not goal % i:
   
6.             goal /= i
   
7.         else:
   
8.             i += 1
   
9.     print(int(goal))

复制代码

Reganrts

回复

Reganrts

？

Cyan_fox

111

906185167

6

RivMarkER

求111

kkhimself

import math

n = 600851475143
t = 0


def is_prime(n):
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True


for i in range(math.isqrt(n) + 1, 1, -1):
    if n % i == 0 and is_prime(i):
        t = i
        break
print(t)

海森漫

正想知道

HuangBin2025

1. def is_prime(num):
   
2.     for i in range(2,int(pow(num,0.5))):
   
3.         if num%i==0:
   
4.             return False
   
5.     else:
   
6.         return True
   
7. for i in range(600851475143,1,-1):
   
8.     if is_prime(i):
   
9.         print(i)
   
10.         break

复制代码