查找C出大量

主要因素我寫了下面的C代碼，找出了大量的大底因子和我的程序在運行時保持執行forever.I試圖通過指定的2 iBigNum withing範圍內進行調試^ 32-1，然後它的工作。查找C出大量

LONG64 iBigNum = 600851475143,iCurr=0,iLarge=0; 
    //600851475143 
    /*4294967295 
     4000000000 
    */iCurr = iBigNum-1; 
    while(iCurr > 0) 
    { 
     if(iBigNum % iCurr == 0){ 
      iLarge=iCurr; 
      break; 
     } 
     iCurr--; 
    } 
    MsgPrintf(TEXT("CustomPrint"),TEXT("%d"),iLarge);

之間，LONG64被定義爲basetsd.h

// 
// The following types are guaranteed to be signed and 64 bits wide. 
// 

typedef __int64 LONG64, *PLONG64;

我運行在Intel Core 2 Duo處理器的代碼爲3.16GHz運行具有4 GB RAM.Is這種預期的行爲？有人能指出我有些方向？謝謝

來源

2014-01-20 ZoomIn

注意：「％d」可能無法與「iBigNum」正常工作。 – chux

@chux感謝，將其改爲「％LD」 – ZoomIn

推薦' 「％I64d號」'[_ _int64]（http://msdn.microsoft.com/en-us/library/aa261215（V = vs.60）。 aspx）或http://stackoverflow.com/questions/3068088/how-to-write-int64-to-cstring – chux

從頂端開始看起來似乎是一個好主意，因爲您需要找到最大的因素，但事實並非如此。可能的最小因子是2，因此最大可能因子是n/2。你花了第一個n/2，即300425737571徒勞無功。這更糟糕的是，你的情況，因爲最小的因素是17

不要嘗試聰明。從底部開始你的分解。當你找到一個因素時，可以用你的號碼除以它，可能要多次，並存儲最後一個因子。停止當你的號碼是1

（這天真的方法仍然是壞的，如果你的號碼是，比方說，一個素數的平方，但是平均，如果你只檢查一個數字，它應該是相當快的。）

編輯：下面是會發現在我上述方式的最大因素的代碼。它會在非素數上合理快速地運行，但在大素數上運行（479001599）需要4秒鐘。 OP的原始輸入是1000多倍。

有了這個警告的方式進行，這裏有雲：

LONG64 max_fact(LONG64 iBigNum) 
{ 
    LONG64 maxFact = 1; 
    LONG64 i = 2; 

    while(iBigNum > 1) 
    { 
     while (iBigNum % i == 0){ 
      iBigNum /= i; 
      maxFact = i; 
     } 
     if (i == 2) i = 3; else i += 2; 
    } 

    return maxFact; 
}

來源

2014-01-20 14:45:09

謝謝，所以現在從2（底部）開始，如果n％2 == 0，那麼最大的素因子將是n/2，否則在其他情況下，增加數量，發現它是否是因子，如果它大於先前的因子，則存儲。直到n /數目爲1.我應用了這個邏輯，但仍然以一個長時間運行的程序:)可能應該嘗試實現由@Sergey L提到的算法 – ZoomIn

如果你需要做很多因素分析，Sergey的解決方案肯定是更好的解決方案。他提供了你需要的所有代碼。我的解決方案具有易於理解和實施的好處。我在編輯的答案中提供了代碼。 –

你的算法是非常緩慢的。這就是爲什麼它似乎永遠運行。

你只減1在同一時間。 2會更合乎邏輯（只檢查奇數除數）
你從頂部做試驗部門。第一個iBigNum/2你將會無所事事，因爲那裏沒有任何因素。

我建議你嘗試實現一個實際的因數分解算法。 Pollards-Rho實現起來非常簡單，並且會在幾分之一毫秒內分解一個64位整數。

#include <stdlib.h> 
#include <stdio.h> 
#include <stdint.h> 
#include <inttypes.h> 

static inline intmax_t pollards_rho_randomiser(intmax_t x, intmax_t n) { 
    return ((x * x) - 1) % n; 
} 

static inline intmax_t gcd(intmax_t x, intmax_t y) { 
    while (y) { 
     intmax_t temp = y; 
     y = x % y; 
     x = temp; 
    } 
    return x; 
} 

intmax_t pollards_rho(intmax_t n) { 
    intmax_t x = 2, y = 2, d = 1; 

    while (d == 1) { 
     x = pollards_rho_randomiser(x,n); 
     y = pollards_rho_randomiser(y,n); 
     y = pollards_rho_randomiser(y,n); 
     d = gcd(abs(x-y), n); 
    } 

    if (d == n) 
     return 0; 
    else 
     return d; 
} 

size_t factorise(intmax_t * factors, intmax_t iBigNum) { 
    size_t num_factors = 0; 

    intmax_t factor; 
    while ((factor = pollards_rho(iBigNum))) { 
     // makes sure to split everything into primes 
     num_factors += factorise(factors + num_factors, factor); 
     iBigNum /= factor; 
    } 

    factors[num_factors++] = iBigNum; 

    return num_factors; 
} 

int compare(const void * a, const void * b) { 
    return *(intmax_t *)b - *(intmax_t *)a; 
} 

int main() { 
    intmax_t iBigNum = 600851475143; 

    intmax_t factors[200]; 
    size_t num_factors = factorise(factors, iBigNum); 

    qsort(factors, num_factors, sizeof(*factors), compare); 
    printf("%" PRIiMAX " = %" PRIiMAX, iBigNum, factors[0]); 

    size_t i; 
    for (i = 1; i < num_factors; i ++) { 
     printf("* %" PRIiMAX, factors[i]); 
    } 

    printf("\n"); 

    return 0; 
}

來源

2014-01-20 17:16:18

回答

相關問題