找到大於N的第一個與M相關的素數

基本上，標題說明了一切。數字不是太大（N的最大值是〜2/3 * max（long），最大值M是max（long）），所以我認爲即使是我現在擁有的簡單解決方案也足夠了。 M是永遠比N.更大找到大於N的第一個與M相關的素數

我目前有：

最簡單的，剛開始從N + 1，執行普通歐幾里德GCD，如果返回1，我們都做了，如果不是遞增，再試一次。

我想知道這種解決方案最糟糕的情況是什麼。性能不是一個大問題，但我仍然覺得必須有更好的方法。

謝謝。

關於最壞的情況下，我做了一個小測試：

Random r = new Random(); 
while (true) 
      { 
       long num = (long) r.Next(); 
       num *= r.Next(); 
       f((long)(num * 0.61), num); 
      } 

... 

public static int max; 

     public static int f(long N, long M) 
     { 
      int iter = 0; 
      while (GCD(N++, M) != 1) 
      { 
       iter++; 
      } 

      if (iter > max) 
      { 
       max = iter; 
       Console.WriteLine(max); 
      } 

      return 0; 
     }

它運行約30分鐘，在最壞的情況下至今29次迭代。所以我相信O（N）有更準確的答案。

來源

2012-02-01 Klark

我不知道最壞的情況，但使用事實，我可以將它限制在292次以上，並且低於53次（消除比率N/M大致是固定的限制）。

令p ，...，P _ķ大於或等於5由其中M爲整除的素數。令N'≥N爲N'= 1 mod 6或N'= 5 mod 6的最小整數。對於每個i = 1，...，k，素數最多除以ceil（49/p _{整數N'，N'+ 6，N'+ 12，...，N'+ 288的上限是Σ_{i = 1，...，k} ceil（49/p _i） Σ_{I = 3，...，16}小區（49/q _我）= 48，其中q是開始其中q爲了素數 = 2（在此之前，因爲Π_{I = 3，...， 17}≥2 意味着M是除2和3以外的至多14個不同的素數的乘積）。我們得出結論所提及的至少一個整數與M相對。}

對於下界，令M = 614889782588491410（前15個素數的乘積）並讓N = 1。在1之後，第一個整數相對於素數前十五個素數是第十三個素數，53.

我希望這兩個邊界都可以在沒有太多工作的情況下進行改進，儘管目前還不清楚。對於上限，分別處理其中2和3都是M的除數的情況，因爲那麼M可以是其他素數的至多十三個的乘積。對於下限，人們可以通過運行Eratosthenes篩選來計算出一個好的M，以計算整數範圍內除這些整數的素數列表。然後掃過範圍內的一扇窗戶;如果窗口中不同素數的產物太大，則推進窗口的尾端;否則，推進前端。

來源

2012-02-01 15:26:07 swen

確保它不是爲O（n），通過了解素數的差距是登錄_Ëñ我們可以簡單地說，你的算法最多登錄_Ë n次迭代，（因爲通過在最後登錄_Ë n號你會看到一個新的素數，這個素數是你給定的數字n），關於這個差距的更多細節，你可以看到prime numbers gap。

因此，對於你有界的情況下，它比登錄_Ê N =登錄_ë < = 44，這將是小於44迭代小。

來源

2012-02-01 17:31:22

找到大於N的第一個與M相關的素數

回答

相關問題