论坛 › 【新】欧拉计划（Project Euler） › 题目3：找出一个合数的最大质数因子

风眠 发表于 2023-8-28 12:51:35

速度很慢，求更优解
def chick(x):
    for i in range(2,x):
      if not x%i:
            return False
    else:
      return True


a=600851475143
for i in range(a//2,0,-1):
    if not a%i:
      if chick(i):
            print(i)
            break

name_Liu 发表于 2023-9-21 14:33:16

1

依瓦尼格 发表于 2023-9-25 00:12:43

学习中{:5_110:}

zhangjinxuan 发表于 2023-10-6 08:55:57

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

Pollard-Rho 呢{:10_277:}{:10_256:}

左右丶 发表于 2023-10-7 21:55:22

讲得很详细，学到了{:10_282:}

chenxyong 发表于 2023-10-11 15:31:29

打卡打卡

AtoposK 发表于 2023-10-15 01:45:36

学会了

AtoposK 发表于 2023-10-15 01:47:43

讲得很好

141319 发表于 2023-10-17 19:38:08

1

141319 发表于 2023-10-17 19:38:29

1

这是豆豆啊 发表于 2023-11-3 16:28:39

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)

居仔爸爸 发表于 2023-11-19 22:09:42

小粪坨屎团团小兔球球

lU553178681 发表于 2023-11-24 14:43:59

学些学习！

sharp46 发表于 2023-11-25 22:09:31

学习学习

奋斗中的鱼 发表于 2023-12-23 17:10:31

{:10_254:}

超神奇葩天才 发表于 2023-12-25 18:39:20

本帖最后由 超神奇葩天才 于 2023-12-25 21:01 编辑

import math
import math
global n
global factor
factor = []
n = int(input())
#n = 600851475143

def _factor():
    global n
    n = int(n)
    for i in range(2,math.isqrt(n)+3):
      if n % i == 0:
            n /= i
            factor.append(i)
            _factor()
      elif n <= i:
            break

_factor()
print(factor[-1])

这个思路怎么样

salt_eto 发表于 2023-12-28 20:31:37

直接枚举，
这题因为因数数量多，欧拉筛效率反而不如穷举
ulong test3(ulong n)
{
ulong res=2;
while(res*res<n)
{
    if(n%res)
    {
      res++;
      continue;
    }
    n/=res;
}
return std::max(res,n);
}

1433391058 发表于 2024-1-4 12:20:15

test

hejiage 发表于 2024-1-4 15:35:26

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

假妖怪 发表于 2024-1-20 00:33:36

真不错

查看完整版本: 题目3：找出一个合数的最大质数因子