13195的主要因子为5、7、13和29。数字600851475143中最大的素因子是什么?
我用自己的方式在Euler项目上解决了这个问题,速度很慢,然后我在某人的github帐户上找到了这个解决方案。我不明白为什么它会起作用。为什么删除了许多因子,这些因子等于一个指数?有什么见解吗?
def Euler3(n=600851475143):
for i in range(2,100000):
while n % i == 0:
n //= i
if n == 1 or n == i:
return i
没有人真正回答你的问题。for循环依次测试每个数字。当i
是
n
的一个因子时,while
循环的测试成功;在这种情况下,它会减少n,然后通过将i与1或n进行比较来检查是否完成。测试是一个
,如果
i
除以n
不止一次,则测试是一个(而不仅仅是
if
)。
虽然很聪明,但这并不是通过试除法进行整数因式分解的正常方式;如果n的系数大于100000,它也不起作用。我在我的博客上有一个解释。这是我的函数版本,它列出了n的所有因子,而不仅仅是最大的因子:
def factors(n):
fs = []
while n % 2 == 0:
fs += [2]
n /= 2
if n == 1:
return fs
f = 3
while f * f <= n:
if n % f == 0:
fs += [f]
n /= f
else:
f += 2
return fs + [n]
此函数分别处理2,然后只尝试奇数因子。它也不限制因子,而是在因子大于剩余的n的平方根时停止,因为在该点n必须是素数。因子是按递增顺序插入的,因此输出列表中的最后一个因子将是最大的,即您想要的因子。
考虑它如何求解n=20:
iteration i=2
while true (20 % 2 == 0)
n = n//2 = 20//2 = 10
if (n == 1 or n == 2) false
while true (10 % 2 == 0)
n = n//2 = 10//2 = 5
if (n == 1 or n == 2) false
while false (5 % 2 == 0)
iteration i = 3
while false (5 % 3 == 0)
iteration i = 4
while false (5 % 4 == 0)
iteration i = 5
while true (5 % 5 == 0)
n = n//5 = 5//5 = 1
if (n == 1 or n == 5) true
return i, which is 5, which is the largest prime factor of 20
它只是删除了一些因子,而且由于它已经删除了许多基本因子(while循环),i的许多值实际上只是白费力气。唯一有机会在循环中做某事的i的值是i的素数。n==i测试涵盖了像25这样的数是素数的平方的情况。但范围似乎有限。对于2*(100000之后的第二大素数),它不会给出正确的答案。
此函数通过查找其输入的连续因子来工作。它发现的第一个因素必然是质数。找到素数因子后,将其从原始数中分割出来,然后继续此过程。当我们把它们全部分开时(留下1或当前因子(i)),我们得到了最后一个(最大的)。
让我们在此处添加一些跟踪代码:
def Euler3(n=600851475143):
for i in range(2,100000):
while n % i == 0:
n //= i
print("Yay, %d is a factor, now we should test %d" % (i, n))
if n == 1 or n == i:
return i
Euler3()
这的输出是:
$ python factor.py
Yay, 71 is a factor, now we should test 8462696833
Yay, 839 is a factor, now we should test 10086647
Yay, 1471 is a factor, now we should test 6857
Yay, 6857 is a factor, now we should test 1
诚然,对于一般的解决方案,范围的顶部应该是n的平方根,但是对于python,调用math.sqrt
返回一个浮点数,所以我认为最初的程序员是在走一条懒惰的捷径。该解决方案一般不会起作用,但对于Euler项目来说已经足够好了。
但算法的其余部分是合理的。
问题 null
问题内容: 例: 第一个参数采用Double并将其保存在该方法范围中。但是,什么是和? 我阅读了这篇文章,却找不到任何相关内容:https : //developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/Methods.html 问题答案: 这就是Swift模仿目标C的命名参
我不禁想到,有一个解决方案只涉及一个循环。有人有想法吗?我更喜欢只使用一个循环的答案,但任何比我目前的效率更高的都是很好的。
其中是我自己的班级。 此方法的返回类型是什么?为什么它似乎有两种返回类型?
项目中element-plus + svg图标这种写法为什么可以生效? icon-peoples是element-plus自带的,还是本地配置的 svg的使用和ElIcon的关系是什么?
问题内容: 我有以下代码: 我希望它能打印a = 2 b = 1,但它却打印相反的东西。因此很明显,swap方法不会交换a和b值。为什么? 问题答案: 这与整数的不变性无关。它与 Java是值传递 ,该死 的事实有关! (不烦恼,只是文章标题:p) 总结一下:您实际上不能在Java中创建交换方法。您只需要在需要的地方自己进行交换即可。反正这只是三行代码,所以应该不成问题:)