Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 스레드전용저장소
- 알고리즘
- 다이나믹 프로그래밍
- 행렬
- 컴퓨터밑바닥의비밀
- column space
- rust 스터디
- 선형대수학
- eigenvalue
- 정보처리기사 실기 벼락치기
- Rust
- vector
- 벡터
- c++
- 컴파일러
- linear algebra
- 정처기 실기 벼락치기
- 정보처리기사 2025 1회 실기 벼락치기
- 다익스트라
- 백준
- 코드포스
- 대상파일
- matrix
- 구문트리
- unity
- 재배치
- 링커
- 정처기 실기 공부법
- CS정리
- 정처기 공부법
Archives
- Today
- Total
개발_기록용
[C++ 에라토스테네스의 체] 소수 판별법 본문
728x90
0. 배경 지식
소수는 1과 자신만을 약수로 갖는 수.
앞서 설명한 약수의 개념이 사용되므로 1부터 N까지 수들 중 소수로 판별해야 한다면
기존의 시간 복잡도에 N을 곱해서 O(N^2) 혹은 O(N √N) 이다.
더 좋은 방법은 소수가 아닌 수들을 걸러내는 것이다.
이 방법이 "에레토스테네스의 체" 이다.
1. 동작 순서
1) 2부터 N까지 모든 정수를 적는다.
2) 아직 지우지 않은 수들 중 가장 작은 소수를 찾는다. 이를 P라 한다.
3) 아직 지우지 않은 수들 중 P의 배수를 크기 순으로 지운다.
4) 아직 모든 수를 지우지 않았다면 다시 2번 단계로 간다.
=> O(N log(log N)) 의 시간 복잡도!
2. 실제 구현법
for(int i=2; i<= N; ++i){
// 아직 지우지 않은 수 중 가장 작은 소수를 찾음.
// bool 자료형 배열 is_prime 안에 모든 요소들에 대해 처음에 True로 초기화.
// 1은 소수가 아니니 i는 2부터 시작.
// j는 i만큼 계속 커지도록 해서, i를 제외한 N이하의 모든 i의 배수를 빠르게 체크.
if(is_prime[i])
{
for(int j = i * 2 ; j <= N ; j+= i)
{
// j가 소수가 아님을 is_prime 배열에 체크.
if(is_prime[j]) is_prime[j] = false;
}
}
}
// 이후 is_prime[i] = true인 모든 i는 소수가 됨.
반응형
'알고리즘' 카테고리의 다른 글
[C++] 유클리드 호제법 - 최대공약수(GCD)와 최소공배수(LCM) (1) | 2024.07.10 |
---|---|
[C++] next_permutation 알고리즘 (2) | 2024.07.08 |
[백준 11055번] 가장 큰 증가하는 부분 수열, C++, 테스트 케이스 (6) | 2024.06.17 |
[CodeForce 327A] Fliping Game C++ 풀이 - Maximum SubArray로 풀기 (0) | 2024.04.08 |
[Codeforce 1003C] C. Intense Heat (0) | 2024.03.15 |
Comments