소수를 구할때 최대로 효율적인 알고리즘을 만드는데 도움이 되는 것인데, 따로 개념을 설명하지는 않겠다.
내가 보기 위한 메모용 글이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include<iostream> #include<math.h> #include<time.h> using namespace std; #define MAX 50001 int num[MAX]; void func(int n){ int sqt = sqrt(n); for(int i=2; i<=sqt;i++){ if(num[i] == 0) continue; for(int j=2*i;j<=n;j+=i){ num[j] = 0; } } } int main(){ clock_t start,end; int n; cin >> n; for(int i=2;i<=n;i++) num[i] = i; start = clock(); func(n); end = clock(); for(int i=2;i<=n;i++){ if(num[i] != 0) cout << num[i] << "\n"; } cout << (double)(end-start) / CLOCKS_PER_SEC << "\n"; } | cs |
'Programming > Algorithm' 카테고리의 다른 글
배낭 알고리즘(Knapsack Algorithm) (0) | 2018.08.23 |
---|---|
최소 공통 조상(Lowest Common Ancestor / LCA) (0) | 2018.08.22 |
벨만 포드 알고리즘 (Bellman-Ford-Moore Algorithm) (0) | 2018.08.22 |
유클리드 호제법(Euclidean algorithm) (0) | 2018.08.22 |
크루스칼 알고리즘(Kruskal's Algorithm) - 최소 신장 트리(Minimum Spanning Tree) (0) | 2018.08.22 |