欧拉计划 发表于 2023-5-29 02:41
出师不捷啊，第三题就出纰漏了！
确实是漏了大的那个因数没有检测是否为质数，刚开始有鱼油指出时我竟 ...
加上检查大的因子是不是也不对呀?
如果n有两个大于Math.sqrt(n)的质数因子a,b;并且a<b
循环的过程中,会先t = b;
再t = a;
最后返回a
还有最后的代码写的,for循环里的i也没用到呀.
import math
n = 600851475143
k = 2
for i in range(0, math.isqrt(n)):
if k >= n:
break
elif n % k == 0:
n = n // k
else:
k = k + 1
print(n)
public static void main(String[] args) {
long res = getSum(600851475143l);
System.out.println(res);
}
private static long getSum(long n) {
long k = 2;
while (k < n) {
if (n % k == 0) {
n = n / k;
} else {
k++;
}
}
return n;
}
looklook
好
速度很慢，求更优解
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
1
学习中{:5_110:}
欧拉计划 发表于 2023-5-31 01:27
刺激啊，复杂度已经降到 O(√n)
Pollard-Rho 呢{:10_277:}{:10_256:}
讲得很详细，学到了{:10_282:}
打卡打卡
学会了
讲得很好
1
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)
小粪坨屎团团小兔球球
学些学习！
学习学习
{:10_254:}