题目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

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

学习中

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

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

Pollard-Rho 呢

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

讲得很详细，学到了

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

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

这是豆豆啊 · 发表于 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

超神奇葩天才 · 发表于 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：找出一个合数的最大质数因子

点评