項目歐拉問題3幫助

Question

我想通過項目歐拉工作，我打了問題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(); 
    } 

Answer 1

對於初學者而言，不是在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. 

Answer 2

你需要減少檢查你正在做的量......想想你需要測試什麼數字。

想要更好的方法閱讀Sieve of Erathosthenes ......它應該讓你指出正確的方向。

Answer 3

嘗試使用Miller-Rabin Primality Test來測試一個數字是否爲素數。這應該會大大加快速度。

Answer 4

雖然問題問的最大首要因素，這並不一定意味着你必須找到一個第一......

Answer 5

其實，對於這種情況，你不需要檢查素性，只是刪除你找到的因素。從n == 2開始並向上掃描。當邪惡大數％n == 0時，將邪惡大數除以n並繼續使用小邪數。當n> = sqrt（big-evil-number）時停止。

在任何現代機器上不應超過幾秒鐘。

Answer 6

至於原因公認nicf的回答是：

它是在歐拉的問題OK，但不使這個在一般情況下有效的解決方案。爲什麼你會嘗試偶數因素？

• 如果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) 

有些模試驗是superflous，當n永遠不能被6，如果所有因素2和3已被刪除分歧。你只能讓我的素數。

只是作爲一個例子讓我們看看結果爲21：

21甚至沒有，所以我們進入與上限開方（21）環（4.6〜）。 然後我們可以將21除以3，因此結果= 3和n = 21/3 = 7。我們現在只需要測試sqrt（7）。它小於3，所以我們完成了for循環。我們返回n和結果的最大值，即n = 7。

Answer 7

另一種方法是首先將所有的質數取爲n/2，然後檢查模數是否爲0. 我用一個算法來獲得所有質量最高爲n可以找到here。

Answer 8

在Java中使用遞歸算法運行時間不到一秒鐘......認爲你的算法有點過於簡單，因爲它包含了一些可以消除的「蠻力」。同樣看看你的解決方案空間如何通過中間計算來減少。

Answer 9

我這樣做的方式是搜索素數（p），從2開始使用Eratosthenes篩。該算法可以在快速機器上找到1000萬以內的所有素數。

對於找到的每個素數，都會將它分成您正在測試的數字，直到您不能再進行整數除法。 （即檢查n % p == 0，如果屬實，則劃分。）

一旦n = 1，您就完成了。成功劃分的n的最後一個值是您的答案。在旁註中，您還發現了所有主要因素n。 PS：如前所述，您只需要搜索2 <= n <= sqrt(p)之間的素數。這使得Eratosthenes的Sieve成爲一個非常快速且易於實現的算法，符合我們的目的。

Answer 10

所有歐拉項目的問題應該少於一分鐘;即使是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 

Answer 11

您可能希望看到這一點： Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

，我喜歡莉兒泥的解決方案：

要求 「mathn.rb」
提出600851475143.prime_division.last.first

我檢查了它here

Answer 12

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; 

這應該足夠快...注意，沒有必要檢查素數...

Answer 13

一旦你找到答案，請在瀏覽器下面;）

http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)

Wofram阿爾法是你的朋友

Answer 14

易peasy在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; 
} 

Answer 15

該解決方案在C++上花了3.7毫秒在我的英特爾四核酷睿i5 iMac（3.1 GHz）

#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; 
} 

Answer 16

也許它被認爲是作弊，但haskell中的一種可能性是寫作（爲了記錄，我自己寫了這些行，並沒有檢查eulerproject線程）;

import Data.Numbers.Primes 
last (primeFactors 600851475143)