项目的欧拉问题3的帮助
-
03-07-2019 - |
题
我在努力工作,通过项目Euler和我打一屏障问题的03.我有一种算法,以作为较小的数字,但是,问题3使用一个非常,非常大的数字。
问题03: 总理因素的13195 5、7、13和29.什么是最大的主要因素的数量600851475143?
这里是我的解决方案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();
}
解决方案
对于初学者而言,不是在n / 2开始搜索,而是在n的平方根处开始。你会得到一半的因素,另一半是他们的补充。
例如:
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.
其他提示
long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3;
while( n > 1)
{
if(n % factor == 0)
{
n/=factor;
}else
factor += 2; //skip even numbrs
}
print factor;
这应该足够快......注意,没有必要检查素数......
实际上,对于这种情况,您不需要检查素性,只需删除您找到的因子。从n == 2开始向上扫描。当邪恶的大数字%n == 0时,将邪恶的大数字除以n并继续使用较小的邪恶数字。当n <!> gt; = sqrt(big-evil-number)时停止。
任何现代机器都不应超过几秒钟。
虽然这个问题要求最大素因子,但这并不一定意味着你必须先找到那个......
您需要减少正在进行的检查量...想一想您需要测试的数字。
为了更好的方法,请阅读 Erathosthenes的筛选 ......它应该得到你指出了正确的方向。
作为为理由接受nicf的回答:
这是确定对所述问题在欧拉,但不会使这一有效的解决方案,在一般的情况。为什么你会尝试甚至数字的因素?
- 如果n甚至是,转左(除 2)直到它没了.如果它是 一个那么,2个是最大总理 的因素。
- 如果n甚至不是,你不需要 测试,甚至数字。
- 这是真的,你可以停在 sqrt(n)。
- 你只需要测试素数为 因素。它可能以更快的速度测试 是否k分n然后测试它 对于素性。
- 你可以优化上限 飞当你找到一个因素。
这会导致一些代码这样的:
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)
有一些模的测试,将变成多余的,因为n永远不能被划分6,如果所有因素2和3已被删除。你只能让素对于我.
只是作为一个例子让我们来看看结果对于21:
21甚至不是,所以我们进入对于循环上限sqrt(21)(~4.6).然后我们可以划分为21 3,因此结果=3,n=21/3=7.我们现在只需要测试达到sqrt(7).这是较小的后3,所以我们完成了对循环。我们回返的最大的n和结果,这是n=7。
我这样做的方法是使用Sieve of Eratosthenes搜索素数(p
),从2开始。该算法可以在速度相当快的机器上找到<!> lt; 2s内的1000万以下的所有素数。
对于您找到的每个素数,测试将其划分为您正在测试的数字,直到您不能再进行整数除法。 (即检查n % p == 0
如果是,则除以。)
一旦n = 1
,你就完成了。成功分割的n
的最后一个值是您的答案。在旁注中,您还找到了2 <= n <= sqrt(p)
的所有主要因素。
PS:如前所述,您只需要在<=>之间搜索素数。这使得Eratosthenes的Sieve成为一种非常快速且易于实现的算法。
找到答案后,在浏览器中输入以下内容;)
http://www.wolframalpha.com/input/?i= FactorInteger(600851475143)
Wofram Alpha是你的朋友
在Java中使用递归算法运行不到一秒......想想你的算法,因为它包含了一些<!>“强制执行<!>”;可以消除。另请参阅如何通过中间计算减少您的解决方案空间。
C ++中的轻松:
#include <iostream>
using namespace std;
int main()
{
unsigned long long int largefactor = 600851475143;
for(int i = 2;;)
{
if (largefactor <= i)
break;
if (largefactor % i == 0)
{
largefactor = largefactor / i;
}
else
i++;
}
cout << largefactor << endl;
cin.get();
return 0;
}
这个C ++解决方案在我的英特尔四核i5 iMac(3.1 GHz)上耗时3.7毫秒
#include <iostream>
#include <cmath>
#include <ctime>
using std::sqrt; using std::cin;
using std::cout; using std::endl;
long lpf(long n)
{
long start = (sqrt(n) + 2 % 2);
if(start % 2 == 0) start++;
for(long i = start; i != 2; i -= 2)
{
if(n % i == 0) //then i is a factor of n
{
long j = 2L;
do {
++j;
}
while(i % j != 0 && j <= i);
if(j == i) //then i is a prime number
return i;
}
}
}
int main()
{
long n, ans;
cout << "Please enter your number: ";
cin >> n; //600851475143L
time_t start, end;
time(&start);
int i;
for(i = 0; i != 3000; ++i)
ans = lpf(n);
time(&end);
cout << "The largest prime factor of your number is: " << ans << endl;
cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;
return 0;
}
所有项目欧拉的问题应该花费不到一分钟;即使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
我喜欢lill mud的解决方案:
require <!> quot; mathn.rb <!> quot;
put 600851475143.prime_division.last.first
我检查了它这里
也许它被认为是作弊,但是haskell的一种可能性就是写(为了记录我自己编写了这些行并且没有检查过eulerproject线程);
import Data.Numbers.Primes
last (primeFactors 600851475143)
尝试使用 Miller-Rabin Primality Test 来测试一个数字是否为素数。这应该会大大加快速度。
另一种方法是首先将所有素数提高到n / 2,然后检查模数是否为0。 我可以找到一个算法,用于获取 n 的所有素数这里。