Post

백준 1456번(S1) - 거의 소수 풀이 정리

Programming, Baekjoon
백준 1456번 오답노트 자료형 오버플로우 부동소숫점 오류
Posted

백준 1456 : 거의 소수


어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

제한 : 1 ≤ A ≤ B ≤ 1014





풀이 과정


처음 접근한 방법은 단순하게 생각해서 문제 그대로 소수를 에라토스테네스의 체로 구한 뒤 그 소수의 A보다 크거나 같고, B보다 작거나 같은 N제곱 꼴의 값들을 구해주는 방식이었음.

즉, 소수를 구하고 그 소수의 제곱꼴 형태의 숫자들을 구하는 것임.

아래는 위 알고리즘을 구현한 코드임.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long int uli;

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
    
    uli a,b;
    cin >> a >> b;
    uli cnt=0;
    vector<uli> primes;
    vector<bool> check(b+1,true);   // bad_alloc error
    check[0]=false;
    check[1]=false;
    for(uli i=2; i<=b; i++) 
    {
        if(check[i]) 
        {
            primes.push_back(i);
            for(uli j=i*2;j<=b;j+=i) 
            {
                check[j]=false;
			}
        }
    }
    
    for(uli i=0; i<primes.size(); i++) 
    {
        uli j=primes[i]*primes[i];
        while(j >= a && j <= b) 
        {
            cnt++;
            j*=primes[i];
        }
    }
    cout << cnt << '\n';
    return 0;
}


코드를 제출하니 런타임 에러 (bad_alloc) 가 발생함.
bad_alloc 에러는 동적 메모리 할당에 실패했을 때 발생하는 에러임.

처음엔 난 동적 메모리 할당(new 연산자)을 해준게 없다고 생각했지만 코드를 보면 vector를 이용하였음.
vector를 생성하면 메모리 heap에 생성되며 동적할당됨. 따라서 vector 변수의 초기화가 실패했다는 뜻임.

바로 이 코드에서 문제가 발생하였음. vector<bool> check(b+1,true);

확인해보니 할당 가능한 크기는 최대 \(10^8\)까지 할당 가능하였음.

여기서 b값이 작으면 문제가 되지 않지만, b 값이 문제 상에서 주어진 MAX 값인 1014가 들어온다면 메모리 할당에 실패하게 되어 에러가 발생함.


그래서 메모리 할당을 어느정도까지 해줘야 하는가 고민하다가 소수를 어디까지 구하는게 좋은지 고민하고, 질문 게시판을 찾아보고 나니 \(10^7\)까지만 구하면 \(10^7\) 이후의 소수의 제곱형태는 1014를 넘어가게 되기 때문에 굳이 구할 필요가 없는 것이었음.

따라서 size 값을 b < \(10^7\) 일 경우 b+1, 이상일 경우에는 10000001로 해주었음.


1
2

uli size = b < 10000000 ? b+1 : 10000001;
vector<bool> check(size,true);


여기서 문제가 또 다시 나타났는데 바로 자료형의 최대 범위를 넘어가는 오버플로우가 나타났음.

기존의 코드를 좀 더 줄여서 소수를 구하는데로 바로 소수의 제곱꼴 형태의 숫자들을 구하였음.


1
2
3
4
5
6

uli k=i*i;                    // i=2 일 때, k=2^2인 4
while(k<=b) 
{
    if(k>=a) { cnt++; }
    k*=i; //                  <---- 오버플로우 
}


문제는 바로 k*=i 이 부분에서 발생하였음.

이 부분에서 계속해서 곱을 해주다보니 숫자가 unsigned long long int 자료형의 범위를 넘어갈 때 오버플로우가 발생하게 되는 것임.

대략 10^19 정도까지 담을 수 있는데, 만약 소수 i의 값이 \(10^7\)이며 while문이 한번이라도 돌게 된다면 1021이 되므로 오버플로우가 일어나므로 제대로 된 검증이 되지 않게 됨.

따라서 틀려버리게 됨. (에러는 나지 않음)

Image Link
acmicpc.net/board/view/66391

image


발생한 문제를 정리하자면..

  1. vector의 동적 메모리 할당 사이즈 문제
  2. 자료형의 오버플로우 문제


1번은 크기를 \(10^7\)로 함으로써 해결이 되었고, 2번이 문제였음.

2번 문제를 해결하려면 어떻게 해야하는가? 2번을 해결하려면 2가지 방법이 있었음.


  1. 값을 변수에 담지 않는 방법
  • (21.12.27 추가), 틀린 방법이었음.
  • 값을 담지 않더라도 애초에 출력 가능한 범위가 정해져있어서 값을 담고 출력할 때 오버플로우가 발생하면 값을 담지 않고 출력하더라도 오버플로우가 일어나게 됨.


  1. 값을 변수에 담되 담는 값을 작게 만드는 방법 -> 루트 값으로 비교
  • 다른 풀이를 보다가 새로운 방법을 알게 되었는데 바로 k의 값을 i로 나누었을 때, 나머지가 0이 아니면 오버플로우가 일어난 것이므로 나가는 것임.
  • 위 내용은 아래에서 설명함


처음엔 2번으로 시도를 하였는데, sqrt 함수를 이용하여 루트 값끼리 비교를 하면 값을 줄일 수 있었음.


1
2
3
4
5
6

double k=sqrt(i)*sqrt(i);
while(k<=sqrt(b)) 
{
    if(k>=sqrt(a)) { cnt++; }
    k=k*sqrt(i);
}


a=1, b=1014일 때, 오버플로우가 나서 틀린 결과 값이 나왔는데 루트로 비교를 하니 결과값이 잘 나와서 성공한 줄 알았지만,,,

8%에서 틀려서 확인해보니 a=4, b=4일 때 출력 값이 0이 나옴. (정답은 1)

그래서 테스트를 해보았음.


1
2
3
4
5
6
7
8
9
10
11
12

int i=2, j=4;
double a = sqrt(double(i))*sqrt(double(i));     // 2

if(a >= sqrt(double(j)))                        // 2 >= 2
{
    cout << "?" << '\n';
}

if(a <= sqrt(double(j)))                        // 2 <= 2
{
    cout << "??" << '\n';
}


위 코드에서 예상 출력 값은 ?, ?? 둘 다 출력될 거라 생각했으나 출력되는 값은 ? 하나뿐이였음. 문제가 무엇인가?

문제는 바로 부동소수점 때문이었음.

a, sqrt( double(j) )의 값을 출력해보면 실제 값은 다르다는 것을 알 수 있음.


1
2
3
4
5
6
7
8
9
10
11

int i=2, j=4;
double a = sqrt(i)*sqrt(i);

printf("a : %.100lf\n", a);
printf("sqrt(j) : %.100lf\n", sqrt(j));

/*
a :       2.000000000000000444089209850062616169452667236328125
sqrt(i) : 1.4142135624
sqrt(j) : 2.000000000000000000000000000000000000000000000000000
*/


따라서 a와 sqrt(j)를 비교를 하면 a > sqrt(j) 이므로 ?만 출력되는 것임.
a와 sqrt(j)는 같지 않다는 것임.


질문을 올리고 나서 답변으로 부동소수점 오류에 대한 게시글을 추천해서 읽어보았음.
acmicpc.net/blog/view/37

sqrt 함수가 안되서 pow 함수를 이용해서 풀어보니 풀렸었음.


1
2
3
4
5
6
7

uli k=2;
while(1) {
    if(pow(i,k) >= a) { 
      if(pow(i,k) <= b) { cnt++; }
		  else {break;}
	  }
		k++;


이거 때문에 처음엔 값을 변수에 담지 않으면 오버플로우가 일어나지 않는구나 라고 생각하게 되었음.

하지만 틀린 사실이란 걸 알게 됨.

자료형의 범위를 벗어난 값은 오버플로우가 일어나서 오히려 값이 줄어들게 된다 이 사실을 몰랐기 때문에 다시 헤맸음.


sqrt 함수를 이용하지 않고 즉, 실수 연산을 하지 않고 하는 방법도 있음.

실수 연산을 하지 않으면서 i와 \(\sqrt j\)를 비교하는 방법이 있는데 예를 들어, \(i \times i = j\)를 \(i = \frac j i\)가 된다는 것임.

따라서 처음엔 이를 토대로 코드를 짰음.


1
2
3
4
5
6

uli k=i;
while(i <= b/k)
{
    if(i >= a/k) { cnt++; }       // wrong, change to if(k*i >= a)
    k*=i;
}


하지만 정답을 얻지는 못해서 질문을 했고 if(i >= a/k) 이 부분을 if(k*i >= a)로 고치니 통과가 되었음.

처음엔 k에 오버플로우 문제가 있어서 k*i로 비교를 하면 오버플로우 가능성이 있는게 아닌가란 생각이 들었으나, 이때는 값을 변수에 담지 않으면 자료형의 범위를 넘어가는 값도 출력할 수 있다. 라고 생각하고 있었음.

무슨 상관이냐면, 아래 코드가 처음에 제출한 오버플로우가 일어나는 코드인데, 위에 코드와 비교해보면 차이점은 while문의 조건이 다르다는 점임.


1
2
3
4
5
6

uli k=i*i;
while(k<=b) 
{
    if(k>=a) { cnt++; }
    k*=i;                         // <---- 오버플로우 
}


내가 이용한 while(i <= b/k)와 바로 위의 코드에 있는 while(k<=b)를 다르게 표현하면 while (true) { ... if (k*i <= b) break; } 임.

여기서 if(i > b / k) 와 if(k*i > b)는 논리적으로는 같아보임.

하지만 차이점은 k*i는 자료형의 범위를 넘어가는 오버플로우가 일어날 수 있는 반면,

b/k는 자료형의 범위가 넘어가는 경우가 일어나지 않기 때문에 (k가 커질수록 계산결과가 줄어들기 때문에) 오버플로우가 발생하지 않게 되는 것이다.

따라서 이 코드를 다음과 같이 수정할 수 있는 것임.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
uli k=i*i;
while(i <= b/k)
{
    if(i >= a/k) { cnt++; }
    k*=i;
}
*/
// 위 코드를 아래로 수정하면 맞음.

uli k=i*i;
while(k<=b)
{
    if(k >= a) { cnt++; }
    if(i > b/k) { break; }                // -> k*i > b
    k*=i;
}

// 또는 

uli k=i;
while(i<=b/k)
{
    if(k*i >= a) { cnt++; }
    k*=i;
}





부동소수점 오류


Link
부동소숫점 오류


정리하면 다음과 같다.

  1. 실수 값을 변수에 모두 담을 수 없다. 변수에 담을 때는 반드시 손실이 일어날 수 밖에 없다. 즉, 실수 변수는 절대 정확한 값을 갖고 있지 않다.

  2. float형보다 double형이 더 느리지만 정확도가 높다. float형의 오차는 \(10^-7\) 정도고 double형은 10-15이다.

  3. 정수가 들어있는 실수형 변수를 정수로 바로 캐스팅하면 안된다. double a=1 (0.9999..)을 int형으로 캐스팅하면 0이 된다.

  4. 비교 연산시 등호를 사용하면 안된다.


문제에 해당되는 부분들은 이 정도이고 그 외에 다른 예시도 있음. (다이아몬드 문제 풀 때 알아야되는 예시 등등)

1,2번 때문에 틀리는 경우가 많으므로 1,2번은 반드시 기억해야 함.





최종 결론


그래서 총 3가지 방법이 있음.

첫 번째는 값을 담지 않고 비교하는 방법

두 번째는 값을 작게 만들어서 비교하되 sqrt 연산으로는 실수 연산을 해야 하므로 실수 연산을 하지 않고 비교하는 방법

세 번째는 오버플로우 발생 시 break 하는 방법이 있음.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef unsigned long long int uli;

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
    
    uli a,b, cnt=0;
    cin >> a >> b;
    uli size = b < 10000000 ? b+1 : 10000001;
    vector<bool> check(size,true);
    check[0]=false;
    check[1]=false;
	
    for(uli i=2; i<size; i++) 
    {
        if(check[i]) 
        {
            for(uli j=i*2;j<size;j+=i) 
            {
                check[j]=false;
            }
            /* 1. pow 함수로 비교하는 방법
            uli k=2;
            while(1) 
            {
                if(pow(i,k) >= a) 
                { 
                    if(pow(i,k) <= b) { cnt++; }
                    else {break;}
                }
                k++;
            }
            */
           
            /* 2. 값을 작게 만들어서 비교하되 실수 연산을 하지 않고 비교하는 방법 
            uli k=i;
            while(i <= b/k)
            {
                if(k*i >= a) { cnt++; }
                k*=i;
            }
            */
            
            // 또는 
            
            /* 3. 오버플로우 발생 시 break 하는 코드
            uli k=i*i;
            while(k<=b) 
            {
                if(k>=a) { cnt++; }
                k*=i;
                if(k%i != 0) { break; } -> 오버플로우 났는지 체크, k는 i의 배수이므로 나머지가 0이어야 함.
            }
            */
        }
    }
	cout << cnt << '\n';
	return 0;
}





Programming, Baekjoon
백준 1456번 오답노트 자료형 오버플로우 부동소숫점 오류
This post is licensed under CC BY 4.0 by the author.