尋找不超過時限的素數

好的第一件事是第一件事。是的，這個問題來自編程比賽。不，我不想欺騙，因爲比賽已經在4小時前結束了。我很確定我的代碼是正確的，但比賽的編譯器說它給出了錯誤的答案。我嘗試了其他編譯器，並說「超出時間限制」。尋找不超過時限的素數

因此，首先，您能否告訴我代碼是否正確？ [一個編譯器說不是]

如果是，那我該如何讓它更省時？ [另一個編譯器認爲很超過時限]

問題的數字被稱爲質數，如果它是大於1且具有不超過1和本身以外的除數。前幾個素數分別是2,3,5,7,11,13等等。給定一個整數X，找到的最小素數不小於X

輸入：第一行包含測試用例T的個數T.T的情況如下。每個測試用例由一個單獨的行中的整數X組成。

輸出：產量T線，一條用於容納最小素數這是不小於X

約束每種情況下：1 < = T < = 10 1 < = X < = 1,000,000

樣品輸入：4 8 47 90 1130

樣本輸出：11 47 97 1151

這裏是我的解決方案：

int main() 
{ 
    int n; 
    long int x, i, a; 
    bool isPrime; // This flag will test if number is prime or not? 
    cin>>n; // Here "n" will represent the number of test cases 
    while(n) 
    { 
     cin>>x; // "x" is the number to be tested for the nth case 

     if(x<=2) 
     { 
      cout<<2<<endl; // All numbers smaller than 3 will have the smallest prime number as 2. 
      continue; 
     } 
     for(i=x;i<=1000000;i++) // Should I have checked values of "i" for odd numbers only? I forgot to try that... Would it have helped in reducing time complexity? 
     { 
      isPrime=true; 
      for(a=2; a<i; a++) // Okay I tried making it (i/2)+1 but then the compiler said that it was a wrong answer. I am skeptical though... 
      { 
       if(i%a==0 and i!=2) 
        isPrime=false; 
      } 
      if(isPrime==true) 
      { 
       cout<<i<<endl; 
       break; 
      } 
     } 

     n--; 
    } 
    return 0; 
}

來源

2013-10-03 user2732146

你試過在你的機器上運行這個嗎？也許編譯器報告錯誤實際上是你的程序運行時間太長（至少比挑戰造成的時間限制多）。 –

是的，我把它運行在我的電腦上，並嘗試過各種測試用例，如：-5,0,1,2,3,50所有這些數字都有正確的輸出。所提供的測試案例也像魅力一樣。 – user2732146

您應該使用緩存來查找已經遇到的主要值。它可能會加快這個過程。你也不需要檢查每個除數，只能達到sqrt（i） – lucasg

爲了避免混淆，使該檢查一個數是否是素數的函數：

bool IsPrime(int x) 
{ 
    isPrime=true; 
    for(int a = 2; a < x; a++) 
    { 
     if (x % a == 0 && a != 2) 
      return false; 
    } 
    return true; 
}

在這裏，我沒有改變你的代碼，只是重組它。這很好，因爲這個功能很小，任何改進都很容易。

刪除邊緣情況

有沒有必要檢查a == 2，因爲你永遠不調用此函數2.這使得內環較小，提供更好的性能。

bool IsPrime(int x) 
{ 
    isPrime=true; 
    for(int a = 2; a < x; a++) 
    { 
     if (x % a == 0) 
      return false; 
    } 
    return true; 
}

檢查更少除數

這是一個衆所周知的事實，以及易查，這足以高達檢查除數，以sqrt(x)。這給了更好的表現！

bool IsPrime(int x) 
{ 
    isPrime=true; 
    for(int a = 2; a * a <= x; a++) 
    { 
     if (x % a == 0) 
      return false; 
    } 
    return true; 
}

此時，您的程序可能會被計時器接受。如果你仍然想要更好的表現，你可以進一步限制除數。

檢查只素因子

嗯，不是真的黃金，但它是很好的限制至少檢查，以奇數。

上埃拉托色尼的篩，其中一些其他的應答者建議的說明：這是很好的，但也許你並不真的需要它，因爲測試用例的數量是非常小的（10）。

編輯：刪除了一些有缺陷的性能分析。

篩分方法需要至少1000000次迭代來構建素數列表。

該試驗方法需要每數小於500次迭代，試圖小於114數字，直到它找到一個素數，並且它確實它的10倍，所以迭代次數小於500 * 114 * 10 = 570000。

來源

2013-10-03 13:48:09 anatolyg

我不會爲您解決，但給你一些提示。

使用Sieve of Eratosthenes，它允許你建立一個數組，你可以用事後知道一個數是不是在O(1)素。
在讀取任何數字之前建立Sieve陣列一次，然後您可以讀取數字並在恆定時間內檢查每個數字。對每個數字執行相同的計算是矯枉過正的。

來源

2013-10-03 13:27:50 mfontanini

因爲這是編程比賽，所以這是行不通的。因爲你需要製作一張素數地圖，這需要很多時間 – ST3

@ ST3你是什麼意思？ – mfontanini

@athabaska OP告訴大家是比賽風格的編程，所以你的時間和記憶有限，這是行不通的，我已經在類似的幾次競賽，我知道規則是。 – ST3

解決沒有時間了這個問題，需要兩兩件事：

預先計算的素數，並
使用二進制搜索

您需要少於78,500質數來預先計算，所以你不必太花哨。你必須做的唯一一件事情就是不要浪費時間檢查你的候選除數與非素數：使用你發現的素數到目前爲止發現新素數。這page has pseudocode for this approach。

由於您發現素數的方式，素數表將按升序排列。對於每個測試用例，使用binary search搜索質數表。雖然線性搜索可能也可以工作，但免費排序時，浪費很多CPU週期毫無意義。此外，C++標準庫has a convenient function for finding items in sorted containers，所以你的搜索可以編碼在一個單一的行。

來源

2013-10-03 13:36:48 dasblinkenlight

你在大數上失敗 - 例如，不小於1,000,000的最小素數是1,000,003。
測試邊緣案例很重要。

然後用Eratosthenes的篩子預先計算素數以加快速度。

來源

2013-10-03 13:48:18 molbdnilo

尋找不超過時限的素數

回答

相關問題