소수 (Prime Number)
소수 : 약수가 자신과 1밖에 없는 수
숫자 N이 소수가 되려면 2보다 크거나 같고,
CASE 1) N-1보다 작거나 같은 자연수로 나눠떨어지면 안된다.
CASE 2) N/2보다 작거나 같은 자연수로 나눠떨어지면 안된다.
이유 : N의 약수 중 자기 자신(N)을 제외한 가장 큰 것은 N/2보다 작거나 같기 때문이다. N=a x b로 나타낼 수 있는데, a가 작을수록 b는 커진다. 가능한 a 중 가장 작은 것은 2이기 때문에 b는 N/2를 넘지 않는다.
CASE 3) 루트N 보다 작거나 같은 자연수로 나눠떨어지면 안된다.
이유 : N을 a로 나눌 수 있다면, N에 대한 a의 보수 b(N=a*b)가 반드시 존재한다. 만약 a>루트N 이면 b<루트N 이다. 그러니 N이 소수인지 알아보기 위해 a까지 검사할 필요는 없다. b를 통해 이미 검사했기 때문이다.
모든 양의 정수는 소수의 곱 형태로 쪼갤 수 있다. 다만 지수 부분이 0인 소수들이 많다는 점은 유의하자…
84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 ...
소수판별
위의 소수가 되기 위한 조건 케이스들을 기반으로 작성한 어떤 수 n이 소수인지 판별하는 법이다.
// CASE 1 : O(n)
bool primeNaive(int n){
if(n<2){
return false;
}
for (int i=2; i<n; i++){
if(n%i == 0){
return false;
}
}
return true;
}
// CASE 2 : O(n/2)
bool primeNaive(int n){
if(n<2){
return false;
}
for (int i=2; i<=n/2; i++){
if(n%i == 0){
return false;
}
}
return true;
}
// CASE 3 : O(루트n)
bool primeNaive(int n){
if(n<2) {
return false;
}
for (int i=2; i*i<=n; i++){
if (n%i == 0){
return false;
}
}
return true;
}
// i*i <= n 은 i <= n루트 와 같다. sqrt()함수를 쓰는 것은 근사값을 나타내기 때문에 이렇게 써주는 것이 좋다고 합니다.
에라토스테네스의 체
에라토스테네스의 체는 소수 목록을 만드는 방법이 굉장히 효율적이다. 이 알고리즘은 소수가 아닌 다른 수들은 다른 소수로 나뉜다는 사실에 기반한다.
에라토스테네스의 체를 이용하면 1부터 N까지 범위 안에 들어가는 모든 소수를 구할 수 있다.
Logic
- 우선 어떤 상한값 크기 N만큼의 리스트를 생성한다.
- 2부터 N까지 모든 수를 써놓는다
- 아직 지워지지 않은 수 중 가장 작은 수를 찾는다
- 그 수는 소수이다.
- 이제 그 수 배수를 모두 지운다.
예시) 2부터 100까지의 모든 수를 써놓는다.
-> 지워지지 않은 수 중 가장 작은 수는 2다. -> 2는 소수이고 2를 제외한 2의 배수를 모두 지운다.
->2 다음으로 작은 수는 3 -> 3은 소수이고 3을 제외한 3의 배수를 모두 지운다.
3 다음으로 작은 수는 5 -> 5는 소수이고 5를 제외한 5의 배수를 모두 지운다.
->5 다음으로 작은 수는 7이다. -> 7은 소수이고 7을 제외한 7의 배수를 모두 지운다.
->7 다음으로 작은 수는 11이다. -> 2,3,5,7의 배수 삭제로 인해 11의 배수는 이미 지워져있다.
11*11은 121로 100을 넘기 때문에, 더 이상 수행할 필요 없다. 따라서 남아있는 모든 수가 소수이다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int aNumberOfPn = 0; // 소수의 개수
bool flag[101] = {0}; // 지워졌으면 true
int n = 100; // 100까지의 소수
/* 소수의 정수배인 수들을 솎아냄
* k<i인 숫자 k에 대한 k*i는
* 앞서 실행된 루프에서 솎아졌을 것이므로
* i*i 부터 시작한다 */
for(int i=2; i<=n; i++){ // 2부터 N까지 모든 소수를 구하는 것이기 때문에, 바깥 for문 i를 n까지 돌린다.
if(flag[i] == false){
cout << "i : " << i << '\n';
for(int j=i*i; j<=n; j+=i){ // j+=i -> j=j+i // i배수 돈다..
flag[j] = true;
}
}
}
return 0;
}