4장 수학 - (5) 소수(Prime Number)
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번 (소수 찾기)