백준 알고리즘 기초 강좌

4장 수학 - (5) 소수(Prime Number)

살구르 2017. 10. 6. 16:34

1. 소수(Prime Number)

-약수가 1과 자기 자신 밖에 없는 수

-1부터 100까지 소수

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97



1) N이 소수가 되려면, 2보다 크거나 같고, N-1 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

(코드)

bool prime(int n){

if(n<2)

return false;

for(int i=2;i<=n-1;i++){

if(n%i==0){

return false;

}

}

return true;

}


=> O(N)


2) N이 소수가 되려면, 2보다 크거나 같고, N/2 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

이유 : N의 약수 중에서 가장 큰 것은 N/2 보다 작거나 같기 때문

N=a*b 로 나타낼 수 있는데, a가 작을수록 b는 크다.

가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.


(코드)

bool prime(int n){

if(n<2)

return false;

for(int i=2;i<=n/2;i++){

if(n%i==0){

return false;

}

}

return true;

}


=> O(N/2) == O(N)


3) N이 소수가 되려면, 2보다 크거나 같고, 루트 N 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

이유 : N이 소수가 아니라면, N=a*b 로 나타낼 수 있다.(a<=b)

두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

따라서, 루트 N 까지만 검사를 해보면 된다.


(코드)

bool prime(int n){

if(n<2)

return false;

for(int i=2;i*i<=n;;i++){

if(n%i==0){

return false;

}

}

return true;

}


=> O(루트N)


-1978번 (소수 찾기)