這是測試特殊素數的最快方法和新方法嗎？

-5

bool is_special_prime (int N) { 
    QHash<int, int> o; 
    struct A_functor 
    { 
    int operator()(unsigned int n) { return n >> __builtin_ctz(n);} 
    }A; 
    int k = A(N + 1); 
    if(k == 1) 
    return 0; 
    o[k] = k; 
    int t = (N - 5) >> 1; 
    for(int i = 0; i < t; i++) { 
     k = A(N + k); 
     if(k == 1 || o.contains(k)) 
     return 0; 
     o[k] = k; 
    } 
    return 1; 
}

是這樣可以測試數字比最新的最大素2^57885161更大 - 1？

來源

2013-05-03 miket

也許你可以解釋算法的作用，以及爲什麼你認爲它可能作爲一個素性測試？即便如此，在這裏可能沒有足夠的前沿數字理論家來驗證你的算法是否正確和新穎。據推測，「N」是潛在梅森素數的指數（例如57885161），而不是素數本身（對於int而言，這顯然太大）。 – 2013-05-03 12:27:05

這是正確的和新穎的。這種方式與int無關，這只是示例代碼。 – miket 2013-05-03 13:18:48

如果你知道這是正確的和新穎的，那麼你爲什麼在這裏問一些模糊的問題，而不是發表你的開創性研究？如果不是，那麼你需要提出一個更清晰的問題;如果不知道單字母變量代表的是什麼以及算術的位數應該達到什麼，那麼代碼有點難以遵循。 – 2013-05-03 13:26:36

您正在通過int類型，該類型可以在32位系統上保存-2^31 to 2^31-1範圍內的數字。您不能用它來測試您提到的訂單號碼

來源

2013-05-03 12:12:34

這是與範圍無關的示例代碼，如果測試數字大於最新的最大素數2^57885161 - 1，則需要更多。 – miket 2013-05-03 13:08:54

這樣可以測試大於最新最大素數2^57885161 - 1的數字嗎？

如果你碰巧使用一個平臺，讓int至少57885162個位寬則是（假設你的算法是正確的，我沒有刻意去查）。

現在，我們只有幾秒鐘嚴重：用消費級電腦現在使用最多64位寬的整數，你可以看到它是從假設的平臺相當長鏡頭......

您需要如果你想要執行這樣的計算，那麼用一個BigNum庫替換int（並且沿途也會有其他限制 - 支撐自己）。

來源

2013-05-03 12:17:31 syam

你讀過盧卡斯 - 萊默爾嗎？這聽起來像你有更多的研究要做，然後才能找到新的更快的方法來測試素數。首先嚐試使用bignum庫實現Lucas-Lehmer。

算法的迭代次數可達N/2，但實際上其速度確實非常慢（遠低於素數）。它也不可能找到大於2^32或2^64的素數，這比2^57885161少很多。你明白爲什麼它如此緩慢？在i小於N/2的值之前，它不能返回1。

我還沒有檢查你的代碼是否準確地確定了素數。

來源

2013-05-03 12:37:22

是的，我之前讀過關於Lucas-Lehmer的文章。它迭代到N/2，但只增加和右移位。你知道盧卡斯 - 萊默需要大規模的平方。 – miket 2013-05-03 13:13:36

@miket但Lucas-Lehmer只需要'O（log N）'算術運算。即使有一個天真的乘法和除法實施，它也會使'N/2'加成並移出水面。 – 2013-05-03 13:24:35

你打賭如果測試2^57885161 - 1盧卡斯 - 萊默需要3年，如果使用最快的電腦，新的只需要不到1秒。 – miket 2013-05-03 13:40:12

這是測試特殊素數的最快方法和新方法嗎？

回答

相關問題