時間複雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的演算法的時間少的會越來越明顯 為什麼呢? 因為在歐拉篩法中,每一個合數只被訪問並將其所對的f[]的值修改了一次。 ...
時間複雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的演算法的時間少的會越來越明顯
為什麼呢?
因為在歐拉篩法中,每一個合數只被訪問並將其所對的f[]的值修改了一次。
for(i = 2; i <= n; i++) { if(f[i] == 0) { p[++cnt] = i; } for(j = 1; j <= cnt; j++) { if(i * p[j] > n)break; f[i * p[j]] = 1; if(i % p[j] == 0)break; } }