[Baekjoon] [1456 : 거의 소수]

이번 문제는 거의 소수라는 문제입니다.

 

알고리즘적으로는 꽤 간단한 편이지만, 오버플로우를 처리하는 등의 꼼수가 필요한 문제였습니다.

DATA 영역과 STACK 영역에 대해서 특성 한 가지를 알게 된 소중한 문제였던 것 같습니다.

 

범위가 주어지면 해당 범위 내에서 소수의 n제곱이 되는 수들의(n >= 2) 갯수를 찾습니다. 갯수를 찾아서 몇 개가 있는지 출력합니다.

 

풀이

---

 

우선 소수가 뭔지를 알아야겠고, 더군다나 범위로 사용을 하니까 에라토스테네스의 체를 사용합니다. 이 때 배열의 최대 크기는 10^7이라고 합니다.

우리가 입력받는 수의 범위는 1 <= A <= B <= 10^14이므로 이것에 유의하여 우선

 

최대 크기로 소수를 구해둡니다.

 

그리고 다시 반복을 2부터 돌려서 (이중 반복문으로)

하나의 소수에 대해 그 곱을 간격으로 반복을 또 돌리는데 해당 수가 범위 내에 있으면 cnt를 1증가시키는 방법으로 해결했습니다.

 

어디선가 계속 Segmentation fault가 나는데.

 

(아 우선 코드는 이것저것 고치다보니 대충..)

#include<stdio.h>
#include<math.h>

int main(void)
{
    long long int a, b;
    long long int arr[1000000] = {1,1};
    int cnt = 0;


    scanf("%lld %lld",&a, &b);

    for(long long int i = 2; i<sqrt(1000000); i++)
    {
        if(arr[i] == 0)
        {
            for(long long int j = i*i; j<1000000; j+=i)
            {
                arr[j] = 1;
            }
        }
    }

    for(long long int i = 2; i<=sqrt(b); i++)
    {
        if(arr[i] == 0)
        {
            for(long long int j = i*i; j<=b; j*=i)
            {
                if(j >= a && j <= b)
                {
                    cnt++;
                    //printf("!%lld ",j);
                }
                if(j*i < 0)
                    break;
            }    
        }
    }

    printf("%d",cnt);
    return 0;
}

나름 이것저것 건들여본 흔적들이 있는데

 

결정적인 것은 배열의 선언이었습니다.

배열 사이즈를 선언하는데 있어 10^7이 안 되었나 암튼

 

 

https://www.acmicpc.net/board/view/5437

글 읽기 - 전역변수와 지역변수의 메모리 사용 차이에 대한 질문...

https://coding-insider.tistory.com/entry/%EC%A7%80%EC%97%AD%EB%B3%80%EC%88%98%EB%A1%9C-%ED%81%AC%EA%B8%B0%EA%B0%80-%ED%81%B0-%EB%B0%B0%EC%97%B4-%EC%84%A0%EC%96%B8-%EC%8B%9C-%EB%AC%B8%EC%A0%9C%EC%A0%90

지역변수로 크기가 큰 배열 선언 시 문제점

 

이것 때문에 좀(많이) 헤맸다.