챕터4-4. 수학 | 소수(Prime Number)

소수(Prime number)

# 두줄 요약
- 연속된 범위에서 소수만 찾아내는 문제는 에라토스테네스의 채를 이용하고,
- 띄엄띄엄 있는 수들을 소수인지 아닌지 따지는 문제라면 소수를 판단하는 세 번째 방법을 이용하자.

 

# 개념
- 1보다 크고 약수가 1과 자기 자신밖에 없는 수
- N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 작은 자연수로 나누어 떨어지면 안된다.

@ 소수를 판단하는 첫 번째 방법 => 하나의 수 당 O(N), N개의 수라면 O(N^2)
- 2보다 크거나 같고, N-1보다 작거나 작은 자연수로 나누어 떨어지면 소수가 아닌 것으로 처리.
- 시간복잡도 O(N)

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), N개의 수라면 O(N^2)
- N이 1과 자신을 제외한 수 '2 ~ n/2' 중 한번이라도 나누어 떨어지게 되면 N은 소수가 아닌 것으로 처리.
- 시간복잡도는 O(1/2N) = O(N)
   -> 반복횟수가 반으로 줄었음에도 불구하고 1/2은 상수이기 때문에 이러함.
- N이 소수가 아닌경우, 1과 자기자신을 제외한 수 a, b로 다음과 같이 표현될 수 있다. N = a x b
   이때, N을 소수로 만들지 않는 가장 작은 약수는 2이고, a = 2 라면 b = N/2가 된다.
   따라서 2~n/2 로 나누어 떨어지는 수는 소수가 아닌 것으로 처리할 수 있다.   
- 왜 따지는 범위를 2~n/2로 하냐하면, 어떤 수 N이 주어지면 2부터 나누어 떨어질지, 3부터 나누어 떨어질 지 알 수 없고
   N이 소수가 아닐 때
   만약 a = 2 라면 b = N/2이다.
   만약 a = 3 라면 b = N/3이다.
   만약 a = 4 라면 b = N/4이다.
   만약 a = ... 라면 b = N/...이다.
   이런식으로 했을 때 a~b의 최대 범위는 2~n/2가 되므로, 이를 범위로 잡아주면 모든 수 N에 적용이 가능하기 때문이다.

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), N개의 수라면 O(N루트N)
- N이 1과 자신을 제외한 수 '2 ~ 루트n' 중 한번이라도 나누어 떨어지게 되면 N은 소수가 아닌 것으로 처리.
- 원리를 그냥 눈에 보이게 표현해보면 소수가 아닌 수 N의 약수를 루트n을 기준으로 둘로 나누어 보면 대칭구조를 가지고 있다.
   ex) 12 의 약수에서 1과 자기자신을 제외한 수 :  2, 3, 4, 6 여기서 루트12는 3.xxx이고 3.xxx를 기준으로 2x6, 3x4가 보여지고 있다. 
   ex) 16 의 약수에서 1과 자기자신을 제외한 수 :  2, 4, 8 여기서 루트16는 4이고 4를 기준으로 2x8이 보여지고 있다.
   이러한 대칭구조를 가지는 원리로 2 ~ 루트n 의 수로 N을 나눴을 때 나누어 떨어지면 소수가 아닌것으로 처리할 수 있다.
- 시간복잡도는 O(루트N)    -> O(N) 1억, O(루트N) :1만 엄청난 차이.
- N이 소수가 아닌경우, 1과 자기자신을 제외한 수 a, b로 다음과 같이 표현될 수 있다. N = a x b
   이 때 a, b 두개의 수중 하나는 루트n 보다 작게 된다.(즉, a <= 루트n 또는 b <= 루트n)
   왜냐하면  a > 루트n 그리고 b > 루트n 인 경우, a * b > N가 되어버리므로 이는 옳지않기 때문이다.
  그러면 다시 N = a x b (a <= 루트n 또는 b <= 루트n) 인 것에서 여기에 a <= b 라는 조건을 추가로 주게 되면
   루트n^2가 n이기 때문에 a는 2 ~ 루트n 이고, b >= 루트n 이 된다.
   그 이유는 a 와 b의 값이 같을 때가 루트n 이고, a는 N의 약수로써 루트n보다 작은 2부터 가능하기 때문에 
   이에 의해 b는 루트n보다 크거나 작아질 수 있는 것이다.

bool prime(int n)
{
    if (n < 2){
        return false;
    
    for (int i = 2; i*i <= n; i++){     // i <= 루트n 으로 넣어주면 실수값이라서 좋지 않으므로 양변을 제곱한 i*i <= n을 사용한다.
        if(n % i == 0)
            return false;
    }
    return true;
}

@ 소수를 판단하는 네 번째 방법(에라토스테네스의 체) => N개의 수에 대해서 O(NloglogN)
- M~N범위안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용하는 것이 가장 빠르다.
1. 2 ~ N까지 모든 수를 써놓는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는데, 그 수는 소수이다.
3. 이제 그 수의 제곱값부터 시작해서 그 수의 배수를 모두 지운다.(그 수의 제곱값이 > N이라면 지울값이 없는 것임)
- 시간복잡도는 바깥for문 O(N) * 안쪽for문 O(loglogN) = O(NloglogN)

- 오버플로우 방지를 위해 아래의 코드에서 두번째 혹은 세번째 방법을 이용하자.
- 주의할 점!!
   아래의 첫번째 방식대로 구현한 경우 n = 1,000,00(십만)인 경우에 i^2에서 1,000,00^2가 정수형의 범위를 넘어가게 된다.
   이를 방지하기 위해서 i^2 값부터 지우는게 아니라, 중복으로 지워도 되니까 그냥 i*2를 사용하기도 한다.
   따라서, i*i 대신에 i*2를 사용해야한다. => 두번째 방식
- 오버플로우를 방지하기 위해 아래의 세번째 방식대로 i*i가 입력받은 n을 넘지 않도록 해주는 방법이 있다.
   j = i*i ~ n는 index로 사용되는 값이기도 하고, 이 index는 n을 넘지 않기때문에 이 방법을 사용할 수 있는 것이다.
   이 방법에서 주의할 점으로는 i가 2~n까지 모든 수를 지나치는게 아니기 때문에 첫번째 방법과 달리
   for문 내부에서 바로바로 소수를 추가하는 것은 불가능하다는 것이다. 소수는 for문이 종료된 이후 check배열을 통해 얻어야 한다.
- m~n 범위의 변경될 경우에도 i가 2부터 저장하여 시작하는 것은 동일해야한다. 그래야 정상적으로 배열이 제거되기 때문이다.
- 두번째 혹은 세번째 방식을 사용하는 것이 좋으며, 
   두번째 방법처럼 바깥 for문에서 i의 범위가 2~n 인경우 안쪽 for문에서 바로 소수를 추가할 수 있으나
   세번째 방법에서는 for문에서 i의 범위가 2~(i*i < n) 까지이므로 안쪽 for문에서 바로 소수를 추가할 수 없다.
   i*i 대신 i*2로 해준 두번째 방식은 중복적인 연산이 존재하기 때문에 세번째 방식보다 불리하기 때문에 4ms정도 더 소요되지만 
   크게 문제될 정도의 시간이 아니기 때문에 소수를 수집하여 컨트롤하기 좋은 두번째 방식을 선호하여 사용하는 것이 더 편하다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<bool> nums(n+1); // index로 저장된 2~N의 숫자를 처리함 (true : 지워진 숫자를 의미, false : 아직 안지운 숫자를 의미)
    vector<int> prime_vec;  // 소수 저장

    for (int i = 2; i <= n; i++) 
    {
        if (nums[i] == false)    
        {
            prime_vec.push_back(i); // i가 2~n까지 모두 값을 가질 수 있다면 이런 구현이 가능한데, 아래의 방식으로 구현하게 되면 이게 먹히지 않으므로 주의해야함.

            for (int j = i * i; j <= n; j += i) // i^2부터 i의 배수를 모두 지워버린다.
                nums[j] = true;
        }
    }

    for (int i = 0; i< prime_vec.size(); i++)
    {
        cout << prime_vec[i]<< "\n";
    }
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m, n;               // 1 <= m <= n <= 1,000,000
    cin >> m >> n;

    vector<int> check(n+1); // 초기값은 defualt로 false임
    vector<int> prime_vec;

    check[0] = true;
    check[1] = true;

    for (int i = 2; i <= n; i++)
    {
        if (check[i] == false)
        {
            if (i >= m)
                prime_vec.push_back(i);

            for (int j = i*2; j <= n; j += i)
                check[j] = true;
        }
    }

    for (int i = 0; i < prime_vec.size(); i++)
    {
        cout << prime_vec[i] << "\n";
    }
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m, n;               // 1 <= m <= n <= 1,000,000
    cin >> m >> n;

    vector<int> check(n+1); // 초기값은 defualt로 false임

    check[0] = true;
    check[1] = true;

    for (int i = 2; i * i <= n; i++) // 내부의 for문에서 i*i부터 check 값을 지워주는데 i*i가 index로 사용되기 때문에 n의 값을 넘을 필요가 없다.
    {
        if (check[i] == false)
        {
            for (int j = i*i; j <= n; j += i)
                check[j] = true;
        }
    }

    for (int i = m; i <= n; i++)
    {
        if (check[i] == false)
            cout << i << "\n";
    }
}

위 개념을 적용한 문제풀이

# 주어진 수 중에서 소수가 몇개인지 구하는 문제
- https://www.acmicpc.net/problem/1978
- 문제에서는 100개의 수만 주어지기 때문에 O(N^2), O(N루트N) 방법 모두 무리없이 가능하다.
- 시간복잡도는 "N개의 숫자 * 1개의 숫자 검사 당 걸리는 시간"으로 구한다. (1개의 숫자 검사 당 걸리는 시간은 방법에 따라 달라진다)

 

# M ~ N이하의 소수를 모두 출력하는 문제
- https://www.acmicpc.net/problem/1929 
- M, N은 1,000,000 이하의 수 이므로
   O(N^2)의 알고리즘을 사용하여 문제를 해결한다면 10^12 = 1000억(1000초)

   O(N로그N)의 알고리즘을 사용하여 문제를 해결한다면 10^9  = 1억(1초)
   의 시간이 걸리므로 위의 두 알고리즘으로는 이 문제를 해결할 수 없다.
- O(NloglogN)의 알고리즘인 에라토스테네스의 채를 사용하여 문제를 해결한다면 
   10^6 loglog10^6 = 10^6 log6 = 약 778151(1초 미만)의 시간이 걸리므로 이 알고리즘은 사용할 수 있다.
- endl을 사용했다가 시간초과가 났었으므로 "\n"을 사용해라.

 

# 골드바흐의 추측 문제
- https://www.acmicpc.net/problem/6588 
- p[i] + b = N          => i번째 소수에다가 뭔가를 더했더니 N이 되냐를 찾을 때 p[i]는 에라토스테네스의 체를 사용하여 찾고
- b = N-p[i] 가 소수인지를 검사하기 위해서 시간복잡도가 O(루트n)인 방법을 사용하면 안되고
   에라토스테네스의 체를 검사할 때 사용한 check 배열에서 check[N-p[i]] == false ? 인지만 검사해주면 
   어떤 수가 소수인지 아닌지를 판단할 수 있다.
- 입력의 수가 최대 10^6개이기 때문에 최소한의 범위내에서 소수를 찾아내기 위한 최소의 숫자를 찾는다면 
   그 시간은 최대 10^6이다. 이럴바에 그냥 어떤 수도 커버가능한 최대의 범위에 대해 소수를 찾아둔다면 
   이것이 효율이 더 좋을 것이다.
- b-a가 가장 큰 경우는 맨 처음 나온 것이 제일 크다.