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

超神奇葩天才 发表于 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

真不错

1Asdusdhjssd 发表于 2024-2-7 13:35:53

学习

gametsbug 发表于 2024-3-23 22:26:04

学习

xiaot1014 发表于 2024-5-21 15:23:00

本帖最后由 xiaot1014 于 2024-5-21 16:33 编辑

if __name__ == '__main__':
    goal = 600851475143
    i = 2
    while goal > i:
      if not goal % i:
            goal /= i
      else:
            i += 1
    print(int(goal))

Reganrts 发表于 2024-7-9 23:42:54

回复

Reganrts 发表于 2024-7-9 23:43:38

？

Cyan_fox 发表于 2024-7-28 19:07:44

111

906185167 发表于 2024-10-20 15:16:04

6

RivMarkER 发表于 2024-12-20 22:20:20

求111

kkhimself 发表于 2024-12-29 23:51:36

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)

海森漫 发表于 2025-3-10 19:28:16

正想知道

HuangBin2025 发表于 2025-4-2 11:37:12

def is_prime(num):
    for i in range(2,int(pow(num,0.5))):
      if num%i==0:
            return False
    else:
      return True
for i in range(600851475143,1,-1):
    if is_prime(i):
      print(i)
      break

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