개발
[Algorithm] 알고리즘 준비 04. 소수, 에라토스테네스의 체
jmob_blog
2018. 8. 30. 15:33
728x90
반응형
소수
소수란?
2나 3과 같이 1과 자신의 수에 의해서만 나누어 떨어지는 수, 또는 2개의 약수만 가지는 수.
모든 자연수는 소수의 곱으로 표현된다.
에라토스테네스의 체
N까지의 숫자가 있다면, 소수의 배수를 순서대로 제거하는 방법
- 1부터 N까지의 수를 배열
- 2는 소수이기 때문에 남겨두고, 2의 배수를 모두 제외 시킴
- 3는 소수이기 때문에 남겨두고, 3의 배수를 모두 제외 시킴
- 다음 수는 4이지만, 이미 2의 배수라 제외 되었음.
- 5는 소수니 남겨두고 5의 배수 모두 제외
...
...
...
- N이 제외된 수가 아니면 N은 소수이며 N의 배수를 모두 제외
해당 방법으로 N 까지 진행한다.
N 까지의 소수를 찾는 법
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 | #include <iostream> using namespace std; bool prime[10001]; int main() { for (int i = 2; i <= 10000; i++) { if (prime[i] == false) { for (int j = i * i ; j <= 1000 ; j += i) { prime[j] = true; } } } for (int i = 2; i < 10000; i++) { if (prime[i] == false) { printf("%d ", i); } } } | cs |
728x90
반응형