C# Project Euler 问题 3 帮助
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/201374/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Project Euler Question 3 Help
提问by Ryan Rodemoyer
I'm trying to work through Project Euler and I'm hitting a barrier on problem 03. I have an algorithm that works for smaller numbers, but problem 3 uses a very, very large number.
我正在尝试通过 Project Euler 并且我在问题 03 上遇到了障碍。我有一个适用于较小数字的算法，但问题 3 使用了一个非常非常大的数字。
Problem 03:The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
问题03：13195的质因数是5、7、13、29，600851475143最大的质因数是多少？
Here is my solution in C# and it's been running for I think close to an hour. I'm not looking for an answer because I do actually want to solve this myself. Mainly just looking for some help.
这是我在 C# 中的解决方案，我认为它已经运行了将近一个小时。我不是在寻找答案，因为我确实想自己解决这个问题。主要是寻求一些帮助。
static void Main(string[] args) {
const long n = 600851475143;
//const long n = 13195;
long count, half, largestPrime = 0;
bool IsAPrime;
half = n / 2;
for (long i = half; i > 1 && largestPrime == 0; i--) {
if (n % i == 0) { // these are factors of n
count = 1;
IsAPrime = true;
while (++count < i && IsAPrime) {
if (i % count == 0) { // does a factor of n have a factor? (not prime)
IsAPrime = false;
}
}
if (IsAPrime) {
largestPrime = i;
}
}
}
Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
Console.ReadLine();
}
采纳答案by nickf
For starters, instead of beginning your search at n / 2, start it at the square root of n. You'll get half of the factors, the other half being their complement.
首先，不要从 n / 2 开始搜索，而是从 n 的平方根开始搜索。你会得到一半的因素，另一半是它们的补充。
eg:
例如：
n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.
回答by Rob Walker
You need to reduce the amount of checking you are doing ... think about what numbers you need to test.
你需要减少你正在做的检查量……想想你需要测试哪些数字。
For a better approach read up on the Sieve of Erathosthenes... it should get you pointed in the right direction.
要获得更好的方法，请阅读Erathosthenes的筛子……它应该让您指向正确的方向。
回答by Nicholas Mancuso
Try using the Miller-Rabin Primality Testto test for a number being prime. That should speed things up considerably.
尝试使用Miller-Rabin 素数测试来测试一个数是否为素数。这应该会大大加快速度。
回答by Bill Barksdale
Although the question asks for the largestprime factor, it doesn't necessarily mean you have to find that one first...
尽管这个问题要求最大的质因数，但这并不一定意味着您必须先找到那个...
回答by JesperE
Actually, for this case you don't need to check for primality, just remove the factors you find. Start with n == 2 and scan upwards. When evil-big-number % n == 0, divide evil-big-number by n and continue with smaller-evil-number. Stop when n >= sqrt(big-evil-number).
实际上，对于这种情况，您不需要检查素性，只需删除您找到的因素。从 n == 2 开始向上扫描。当 evil-big-number % n == 0 时，将 evil-big-number 除以 n 并继续使用 small-evil-number。当 n >= sqrt(big-evil-number) 时停止。
Should not take more than a few seconds on any modern machine.
在任何现代机器上花费的时间不应超过几秒钟。
回答by Ralph M. Rickenbach
As for the reason to accepted nicf's answer:
至于接受nicf回答的原因：
It is OK for the problem at Euler, but does not make this an efficient solution in the general case. Why would you try even numbers for factors?
Euler 上的问题是可以的，但在一般情况下并不能使其成为有效的解决方案。为什么要尝试偶数的因数？
- If n is even, shift left (divide by 2) until it is not anymore. If it is one then, 2 is the largest prime factor.
- If n is not even, you do not have to test even numbers.
- It is true that you can stop at sqrt(n).
- You only have to test primes for factors. It might be faster to test whether k divides n and then test it for primality though.
- You can optimize the upper limit on the fly when you find a factor.
- 如果 n 是偶数，则左移（除以 2）直到不再是。如果是 1，则 2 是最大的质因数。
- 如果 n 不是偶数，则不必测试偶数。
- 确实可以停在sqrt(n)。
- 您只需要测试因数的素数。测试 k 是否除以 n 然后测试它的素性可能会更快。
- 当您找到一个因子时，您可以即时优化上限。
This would lead to some code like this:
这将导致一些像这样的代码：
n = abs(number);
result = 1;
if (n mod 2 = 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i = 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result)
There are some modulo tests that are superflous, as n can never be divided by 6 if all factors 2 and 3 have been removed. You could only allow primes for i.
有一些模测试是多余的，因为如果删除了所有因子 2 和 3，n 永远不能被 6 整除。您只能允许 i 为素数。
Just as an example lets look at the result for 21:
举个例子，让我们看看 21 的结果：
21 is not even, so we go into the for loop with upper limit sqrt(21) (~4.6). We can then divide 21 by 3, therefore result = 3 and n = 21/3 = 7. We now only have to test up to sqrt(7). which is smaller then 3, so we are done with the for loop. We return the max of n and result, which is n = 7.
21 不是偶数，因此我们进入具有上限 sqrt(21) (~4.6) 的 for 循环。然后我们可以将 21 除以 3，因此结果 = 3 且 n = 21/3 = 7。我们现在只需要测试 sqrt(7)。它小于 3，所以我们完成了 for 循环。我们返回 n 和结果的最大值，即 n = 7。
回答by AquilaX
回答by Steve Moyer
Using a recursive algorithm in Java runs less than a second ... think your algorithm through a bit as it includes some "brute-forcing" that can be eliminated. Also look at how your solution space can be reduced by intermediate calculations.
在 Java 中使用递归算法运行不到一秒钟......仔细思考你的算法，因为它包含一些可以消除的“蛮力”。还要看看如何通过中间计算来减少您的解决方案空间。
回答by Matthew Scharley
The way I did it was to search for primes (p), starting at 2 using the Sieve of Eratosthenes. This algorithm can find all the primes under 10 million in <2s on a decently fast machine.
我这样做的方法是p使用埃拉托色尼筛法从 2 开始搜索素数 ( )。该算法可以在速度相当快的机器上在 <2 秒内找到 1000 万以下的所有质数。
For every prime you find, test divide it into the number you are testing against untill you can't do integer division anymore. (ie. check n % p == 0and if true, then divide.)
对于您找到的每个素数，测试将其划分为您正在测试的数字，直到您不能再进行整数除法。（即检查n % p == 0，如果为真，则除以。）
Once n = 1, you're done. The last value of nthat successfully divided is your answer. On a sidenote, you've also found all the prime factors of non the way.
一次n = 1，你就完成了。n成功划分的最后一个值就是你的答案。在旁注中，您还发现了所有的主要因素n。
PS: As been noted before, you only need to search for primes between 2 <= n <= sqrt(p). This makes the Sieve of Eratosthenes a very fast and easy to implement algorithm for our purposes.
PS：如前所述，您只需要在2 <= n <= sqrt(p). 这使得 Eratosthenes 筛法成为我们目的的一种非常快速且易于实现的算法。
回答by jfs
All Project Euler's problems should take less then a minute; even an unoptimized recursive implementation in Python takes less then a second [0.09 secs (cpu 4.3GHz)].
欧拉计划的所有问题都应该不到一分钟；即使在 Python 中未优化的递归实现也只需不到一秒 [0.09 秒 (cpu 4.3GHz)]。
from math import sqrt
def largest_primefactor(number):
for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
q, r = divmod(number, divisor)
if r == 0:
#assert(isprime(divisor))
# recursion depth == number of prime factors,
# e.g. 4 has two prime factors: {2,2}
return largest_primefactor(q)
return number # number is a prime itself
