Prime Problems

Eratosthese sieve method

• 用一bool array判斷是否為質數
• 1 表示可能為質數
• 0 表示不為質數
• 若 i 確定是質數，則arr[k] = 0，其中k為i的整數倍
• Time Complexity: $O(n logn)$

Implementation

for (i = 2; i <= n; i++) a[i] = 1;
for (i = 2; i <= n; i++) {
    if (a[i]) {
        cout << i << endl;
        k = i * i;
        while (k <= n) {
          a[k] = 0;
          k = k + i;
        }
    }
}