[알고리즘] 소수,에라토스테네스의 체

 

##소수(prime)

1,알고리즘

1) n이 소수인지 판별

 

(1) 완전탐색

: 2~n-1 까지 약수 있는지 검사

-시간복잡도:O(n)

 

(2) 루트n 까지

: 1~sqrt(n) 까지 나누어 떨어지는지 검사

 

-시간복잡도:O(sqrt(n))

 

for (int i = 2; i * i <= num; i++) { // 루트n 은 i*i<n 이렇게 구현
 
if (num % i == 0) { return false; }
 
}

(3) 에라토스테네스의 체

: 2부터 시작해 각 수의 모든 배수들은 소수가 아니므로 제거

-시간복잡도 가장 빠름

 

// 에라토스테네스 체
void eratos() {
    check[0] = check[1] = 1;
    for (int i = 2; i*i <= 1000000; i++) { // 루트100만 까지 , 넘어가면 이미 다 소수판별 되있음
        if (check[i] == 0) {
            for (int j = i + i; j <= 1000000; j += i) { // i의 배수들 소수아님 처리
                check[j] = 1;
            }
        }
    }
}

2) n까지 소수 구하기