[백준] 1016

여기서 핵심은 max값과 min값의 차가 10만이하라는 점이다.

처음에 실패한 코드를 보면

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

int main() {
    long long a, b;
    long nono = 0;
    long long index = 2;
    bool isNONO = true;

    // 데이터 읽기
    scanf("%lld %lld", &a, &b);

    // ㄴㄴ 찾기
    for (long number = a; number <= b; number++) {
        index = 2;
        while (index * index <= number) {
            if (!(number % (index * index))) {
                isNONO = false;
                break;
            }
            index++;
        }

        if (isNONO) {
            nono++;
        }
        else {
            isNONO = true;
        }
    }

    printf("%d", nono);
}

일단 값들이 크므로 a와 b의 데이터 타입을 long long으로 선언했다. 그 다음 뻔하지만 a부터 b까지 for문을 돌리면서 그 값보다 작은 제곱수들을 하나하나 나누고 그 값을 if문으로 따지면서 코드를 짰다.

하지만 이 문제가 어려운 이유는 바로 그렇게 여유롭게 for문 안에 if 문을 넣는 것을 허락하지 않는다는 것이다. 당연히 시간초과가 나왔고 그래서 그 다음으로 에라토스테네스의 체 알고리즘을 이용했다.

기존에는 소수를 찾으려고 만든 알고리즘이다. 간단하다. 2부터 100중에 소수를 찾으려고 한다면 100개의 배열을 만들고 값들을 0으로 초기화한다. 그리고 2의 배수들 중에서 2를 제외하고 ( 4, 6..., 100) 1로 초기화한다. 3의 배수, 5의 배수 쭉쭉 시행해갔을 때 배열의 값이 0으로 남아있는 것들이 소수이다.

이 알고리즘과 max값과 min값의 차가 10만이하라는 점을 이용해서 새로 소스코드를 작성했다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main() {
    long long min, max;
    bool sieve[1000002];
    long long result = 0;
    // 데이터 읽기

    scanf("%lld %lld", &min, &max);

    // 모든 sieve를 1로 초기화
    for (long long i = 0; i < 1000002; i++) {
        sieve[i] = 1;
    }
    // ㄴㄴ 찾기
    for (long long i = 2; i <= sqrt(max); i++) {
        long long square = i * i;
        long long startIdx = (min - 1) / (square);
        for (long long j = startIdx * square + square; j <= max; j = j + square) { 
            sieve[j - min] = 0;
        }
    }
    
    for (long long i = 0; i <= max - min; i++) {
        result += sieve[i];
    }

    printf("%lld", result);
}

먼저 sieve 변수를 모두 1로 초기화하고 제곱수의 배수를 배열에서 지워나갔다. nested for문의 inner문의 조건문과 그 윗줄을 보면은 제곱수의 배수들 중에서 min과 max 사이에 있는 값들만 찾아내는 핵심 로직을 볼 수 있다.

그리고 문제를 풀면서 long long에 익숙치 않아서 for문에서 index를 선언할 때 int형으로 선언했더니 최대값을 넘어가면서(음수가 된다) index 범위 오류가 발생하기도 했다. 정해진 범위를 넘어서면 오버플로우나 언더플로우가 발생하면서 값의 부호가 달라진다는 점을 유의하고 정수의 크기가 부족하다면 int가 아니라 long 이나 long long, 그마저도 부족하다면 unsigned long long을 이용해보자.