Optimizating素數序列

我堅持從Codechef實踐問題難度介質的問題，有問題的聲明：Optimizating素數序列

Shridhar要產生自己的密碼一些素數。幫助他！你的任務是兩個給定數字

Rest of the description, I/O format, Test cases examples on this question link

我的執行是得到一個TLE（時間超出限制）的問題，並希望解決這個問題之間產生的所有素數，你可以指出任何在我的實施中出現了問題，我似乎無法在空轉幾個小時後弄清楚。

包括指令和ifPrime功能

#include<map> 
#include<math.h> 
#include<stdio.h> 
#define LLD long long int 
#define REPNE(i,a,b) for(LLD i=a; i<=b; ++i) 
#define REPNEI(i,a,b,k) for(LLD i=a; i<=b; i+=k) 
using namespace std; 

map<LLD, bool> mem; 

bool ifPrime (LLD a) { 
    if (a<2) return false; 
    else if (a==2) return true; 
    else if (a%2==0) return false; 

    REPNEI(i,3,sqrt(a),2) { 
     if (a%i==0) return false; 
    } 

    mem[a] = true; 
    return true; 
}

生成主要功能

void genPrime (LLD a, LLD b) { 
    REPNE(i,a,b) { 
     if (mem.find(i) != mem.end()) printf("%lld\n", i); 
     else if (ifPrime(i)) printf("%lld\n", i); 
    } printf("\n"); 
}

主要

int main () { 
    // freopen("input.txt", "r", stdin); 

    int t; scanf("%d", &t); 
    REPNE(test, 1, t) { 
     LLD a, b; 
     scanf("%lld %lld", &a, &b); 

     genPrime(a,b); 

    } 
}

我想不出其他的解決這個問題，唯一的辦法我想到了memoization，它也處理大整數。需要幫助。

來源

2017-07-19 Imran Mirza

你真的認爲'REPNE'比簡單循環更具可讀性嗎？ – Jarod42

您可以使用[Sieve_of_Eratosthenes]（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）。 – Jarod42

參與競爭性編程的人發現宏比編寫完整循環更容易，因爲速度在競爭中確實很重要，因爲在實際的現場開發中，應該避免這些以確保團隊成員之間的可讀性@ Jarod42 –

該方法存在一個問題，即它正在生成記憶鍵，值對。可能他們應該立即測試而不是保存它們。

一個簡單的解決方案是迭代範圍m<=x<=n，然後使用優化的主要檢查算法（O（（nm）^ 1/2））檢查數字是否爲素數，這對於非常非常安靜大數。

主要功能

bool ifPrime (int n) { 
    if (n==2) return true; 
    else if (n%2==0 || n<=1) return false; 
    for (int i=3; i<=sqrt(n); i+=2) { 
     if (n%i==0) return false; 
    } 

    return true; 
}

，你主要作爲

int main () { 
    int t; scanf("%d", &t); 
    REPNE(test, 1, t) { 
     LLD a, b; 
     scanf("%lld %lld", &a, &b); 

     REPNE(i,a,b) { 
      if (ifPrime(i)) printf("%lld\n", i); 
     } printf("\n"); 
    } 
}

我已經按照你的宏定義試圖代碼，希望它有助於:)

來源

2017-07-19 08:04:44

非常感謝！這個實現工作完美，安靜易於理解，再加上codechef判斷爲所有情況提供了一個接受的答案+1 –

...考慮到編譯器優化了對sqrt（n）的重複調用... –

你應該考慮使用std :: unordered_map而不是std :: map。 std :: map通常用樹來實現，而std :: unordered_map用哈希表來實現。現代計算機上的散列表操作通常比樹上的操作要快。

來源

2017-09-15 14:22:32

Optimizating素數序列

回答

相關問題