破解项目欧拉问题3，我的解决方案正确吗? [英] Taking a crack at project euler problem 3, is my solution correct?
问题描述
欧拉计划的问题3内容如下:
13195的主要因子是5、7、13和29. 600851475143中最大的素数是多少?
我已经提出了这个解决方案，很有意义，看起来还不错，适用于小数字，但是当我们遇到问题的时候，这个数字就是程序永远运行的时候.我的问题是，这从根本上是正确的，如果可以的话，我该如何优化代码?以我的理解，有问题的函数是is_prime().
bool is_factor(long long int num, long long int factor)
{
if(!(num%factor))
{
return true;
}
else
{
return false;
}
}
bool is_prime(long long int num)
{
long long int i;
bool flag = true;
for(i = 2; i <= num/2; i++)
{
if(!(num%i))
{
flag = false;
}
}
return flag;
}
int main(void)
{
long long int i, max_factor = 1;
for(i = 1; i < 600851475143; i++)
{
if(is_factor(600851475143,i) && is_prime(i) && i>max_factor)
{
max_factor = i;
}
}
printf("%d\n",max_factor);
return 0;
}
到目前为止，您在总体上使用的一般策略如下:
- 尝试将目标数字除以所有小于或等于目标数字一半的数字.
- 每次找到除数时，请查看它是否是质数并且大于最大因数.如果是这样，请更新最大因子.
- 返回以这种方式找到的最大数字.
考虑到您的目标是找到单个数字的最大因子，所以这是一个相当合理的策略.有两种方法可以加快此速度.其中有些在评论中回显，而另一些(据我所知)尚未在其中提出.
优化1:消除原始性检查
现在，您将目标数除以每个可能的除数，然后检查这些除数是否为质数.如果您的目标数量有很多除数，那么您将花费大量时间检查不是质数的除数，这会占用您的运行时间.
一种替代方法如下.与以前一样，尝试按顺序将目标数除以每个可能的除数.但是，请做一个更改:只要找到除数，就可以通过除以该除数的尽可能多的副本来修改目标编号.如果执行此操作，则会发生一些有趣的事情:将发现除以该数字的唯一数字将是质数.
这是为什么?
要了解原因，请考虑这将如何工作.您首先要测试2是否将数字除.如果是这样，则将尽可能多地分割2的副本，这意味着如果以后尝试除以2的倍数的任何数字，则会发现较大的数字不是除数.
类似地，您然后将测试3是否将数字除.如果是这样，您将除以3的所有副本，因此不会是除以3的倍数的数字.
此更改无需使用is_prime功能，从而节省了大量工作.另外，可以保证您以这种方式找到的任何除数都是质数.
优化2:尽早停止
您当前的代码通过在候选除数大于目标数的一半时立即停止搜索除数来工作.如果您通常在寻找除数，这是您可以做的最好的事情.但是，如果您首先进行上述优化，则可以在此之前停止.
上述将您遇到的所有主要因素明确分开的策略还有一个额外的好处.假设完成所有除法后，您剩余的目标编号为n.现在，假设您当前的除数为d并且d< n.如果d除以n，则可以将n写为两个数字d和n / d的乘积.因为您一直用目标数除以遇到的所有素数，所以我们保证n的素数不小于d.也就是说，如果n / d< d，则d不能是n的除数.为什么?因为，如果d确实除了n，则数字n / d必须具有小于d的素数，但是我们知道n没有这样的素数.
因此，当您尝试除数时，只要n / d< d，或者等价地，只要n< d 2 .一旦发生这种情况，您就会知道n不再具有除其以外的素数，因此剩余数n是最后一个素数.
在实践中，这将大大加快速度.您的目标数字约为10 12 ，并且您可以在最后一个约数大致等于该数字的平方根(即10 6 )时停止.这意味着您只需要搜索一百万个因数，而不是一万亿个！
优化3:智能选择除数
以上两个优化或多或少地反映了您的原始策略，可能足以让您获得答案并每天称呼它.但是，如果您只是出于娱乐目的想加快速度，则可以考虑尝试更好地选择除数.
例如，现在，您尝试除以目标的数字中有一半是偶数.除了2，没有偶数是素数，因此您可以考虑将循环分为两部分:一种特殊情况，用于处理2，一个循环从3开始计数，步长为2(3、5、7， 9、11、13等)，而不是大小为1的步长.(盯着目标数字，您会发现它不是偶数，因此您甚至可以完全跳过除以2！)
更好的是，考虑下载最多约10 7 的所有质数的列表.可以将该列表硬编码到您的程序中，或者将其全部转储到文本文件中并在程序启动时读取.然后，仅将目标除以该列表上的数字.瞧！现在，您只需除以质数即可，从而节省了大量时间和精力. (素数定理说，只有大约ln 10 7 ≈ 18.4的数字小于10 7 才是质数，因此可能会给您额外20倍的加速最重要的事情.
希望这会有所帮助！
Problem 3 of Project Euler reads as follows:
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
I've made this solution, makes sense, looks okay, works for small numbers but when we get to the problem's huge number is when the program runs forever. My question is, is this fundamentally correct, and if so how could i optimize the code? In my understanding, the problematic function is is_prime().
bool is_factor(long long int num, long long int factor)
{
if(!(num%factor))
{
return true;
}
else
{
return false;
}
}
bool is_prime(long long int num)
{
long long int i;
bool flag = true;
for(i = 2; i <= num/2; i++)
{
if(!(num%i))
{
flag = false;
}
}
return flag;
}
int main(void)
{
long long int i, max_factor = 1;
for(i = 1; i < 600851475143; i++)
{
if(is_factor(600851475143,i) && is_prime(i) && i>max_factor)
{
max_factor = i;
}
}
printf("%d\n",max_factor);
return 0;
}
The general strategy you're using so far, at a high level, looks like this:
- Try dividing the target number by all numbers less than or equal to half the target number.
- Each time you find a divisor, see if it's a prime number and bigger than the maximum factor. If so, update the maximum factor.
- Return the largest number you find this way.
Considering that your goal is to find the largest factor of a single number, this is a fairly reasonable strategy. There are a couple of ways that you could speed this up. Some of them are echoed in the comments, while others (to the best of my knowledge) haven't been proposed there.
Optimization 1: Eliminate the Primality Checking
Right now, you're proceeding by dividing the target number by each possible divisor, then checking whether those divisors are prime numbers. If your target number has a lot of divisors, then you're going to spend a lot of time checking divisors that aren't prime, which will eat into your runtime.
An alternative approach would be the following. As before, try dividing the target number by each possible divisor, in order. However, make one change: whenever you find a divisor, modify the target number by dividing out as many copies of that divisor as possible. If you do this, something interesting happens: the only numbers that you'll discover divide the number will be prime numbers.
Why is this?
To see why, think about how this will work. You'll first test whether 2 divides the number. If so, you'll divide out as many copies of 2 as is possible, meaning that if you try dividing by any number that's a multiple of 2 later on, you'll find that the larger number isn't a divisor.
Similarly, you'll then test whether 3 divides the number. If so, you'll divide out all the copies of 3, so no number that is a multiple of three will ever divide the remaining number.
This single change eliminates the need for the is_prime function, saving a ton of work. Plus, you can be guaranteed that any divisor you find this way will be a prime number.
Optimization 2: Stopping Early
Your current code works by stopping the search for divisors as soon as the candidate divisor is greater than half the target number. If you're looking for divisors in general, this is the best that you can do. However, if you begin by making the above optimization, you can stop even earlier than this.
The above strategy of cleanly dividing out all prime factors you encounter has an added benefit. Suppose that, after all the dividing that's been done, your remaining target number is n. Now, imagine that your current divisor is d and that d < n. If d divides n, then you can write n as the product of the two numbers d and n / d. Because you've been dividing the target number through by all prime factors you encounter, we're guaranteed that n has no prime factors less than d. That means, in turn, that if n / d < d, then d can't be a divisor of n. Why? Because, if d did divide n, then the number n / d would have to have a prime factor less than d, but we know that n has no such prime factors.
As a result, as you're trying out divisors, you can stop as soon as n / d < d, or, equivalently, as soon as n < d2. Once that happens, you know that n no longer has any prime factors less than itself, so the leftover number n is the last prime divisor.
In practice, this will dramatically speed things up. Your target number is roughly 1012, and you can stop as soon as the last divisor is roughly on the order of the square root of that number, which is around 106. That means you only need to search a million divisors, not a trillion!
Optimization 3: Choose Divisors Intelligently
The two above optimizations, which more or less reflect your original strategy, will likely be enough for you to get your answer and call it a day. However, if you'd like to speed things up a bit more just for the fun of it, you could consider trying to select your divisors a bit better.
Right now, for example, half of the numbers you try dividing the target by are even. Aside from 2, no even number is prime, so you could consider splitting your loop into two pieces: a special-case to handle 2, and a loop that starts counting at 3 and takes steps of size 2 (3, 5, 7, 9, 11, 13, etc.) rather than steps of size 1. (Eyeballing the target number, you can see that it's not even, so you could even skip division by 2 entirely!)
Even better, consider downloading a list of all the prime numbers up to approximately 107. Either hardcode that list into your program, or dump it all into a text file and read it in at program startup. Then, only divide the target by the numbers on that list. Voila! You're now only dividing by prime numbers, saving you a lot of time and effort. (The Prime Number Theorem says that only about ln 107 ≈ 18.4 numbers less than 107 will be prime, so that's likely going to give you an extra 20x speedup on top of everything else.
Hope this helps!
这篇关于破解项目欧拉问题3，我的解决方案正确吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
