HDU 1216 幸运數：篩選法生成幸存數列（非質數篩）

問題描述

從自然數列 2,3,4,5,... 開始：
1. 取第一個數 2，刪除其後每隔 2 個數。
2. 取下一個幸存數 3，刪除其後每隔 3 個數。
3. 重複上述過程，求前 3000 個幸存數。
這是**幸运數**數列，與質數篩相似但規則不同。

模擬算法

const int MAXN = 50000; // 足夠大
bool del[MAXN];
int lucky[3005];

int main() {
    int cnt = 0;
    for (int i=2; i= 3000) break;
            int step = i, k = 0;
            for (int j=i+1; j>n, n) cout << lucky[n-1] << "\n";
}

關鍵點

• 外層遍歷自然數，內層遍歷**未刪除**的數計數刪除。
• MAXN=50000 經驗足夠產生 3000 個幸运數（第 3000 個約 35000）。
• 預計算後查詢 O(1)。

與質數篩對比