에라토스테네스의 체 범위
2019. 7. 1. 15:03ㆍ알고리즘/암기
기본적인 소수 알고리즘을 구현할 때의 질문은 "임의의 수 N은 소수입니까"에서 시작된다.
N을 소인수분해해서 a와 b로 나눌 수 있고, a < b인 대소관계가 지켜질 때 a가 가장 클 때는 a와 b 모두 루트 N이 되었을 때다.
이 개념을 에라토스테네스의 체에 도입한다면, 임의의 N까지 탐색을 한다면 루트 N까지만 탐색을 해도 "다음 루프에서 제곱꼴로 탐색을 하기 때문에" 문제가 없다
예제소스코드
'알고리즘 > 암기' 카테고리의 다른 글
| memset 사용 시 주의할 점 (0) | 2019.07.03 |
|---|---|
| 에라토스테네스의 체 비트마스크로 메모리 줄이기 (0) | 2019.07.01 |
| gcc/g++ 비트마스크에서의 집합의 크기와 최소 원소 (0) | 2019.07.01 |
| strlen을 for문에서 사용시 주의할 점 (0) | 2019.07.01 |
| 3의 배수 특징 (0) | 2019.06.30 |