[10일차] [DP2] 소수의 합

- 문제 설명

a와 b사이의 소수들의 합을 구하여라

a가 2고 b가 7이라면 3+5로 8이다.

- 입력

1 // 테스트 케이스

1 10 // 1< <10 사이

- 출력

#1 17 // 테스트케이스, 소수들의 합

- 입력 예시

3
1 10
5 20
100 1000

- 출력 예시

#1 17
#2 67
#3 75067

-코드

#include "stdio.h"

long long primeNumber[1000001]; // 소수 테이블

long long int sum; // 소수들의 합

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int startNumber, endNumber;

        scanf("%d %d",&startNumber, &endNumber); // startNumer < < endNumber 사이

        for(int i=1;i<=endNumber;i++) // 일단 자연수로 채움

            primeNumber[i] = i;

        primeNumber[1] = 0; // 1은 소수가 아니므로 0으로 초기화

        for(int i=2;i*i<=endNumber;i++) // 2부터 i*i가 endNumber보다 작은 경우

        {

            if(primeNumber[i] != 0)

            {

                for(int j=2;j*i<=endNumber;j++)

                {

                    primeNumber[j*i] = 0;

                }

            }

        }

        sum = 0; // 합 초기화

        for(int i=startNumber+1;i<endNumber;i++)

        {

            if (primeNumber[i] != 0) // 소수인 경우

            {

                sum+=primeNumber[i]; // 더해줌

            }

        }

        printf("#%d %lld\n", tc,sum);

    }

    return 0;

}

- 소수 테이블을 채울때 i * i가  endNumber보다 작게 도는 이유

16의 약수를 생각해 보자

1 * 16

2 * 8

4* 4

8 * 2

16 * 1

위와 같다.

위에서 4*4이후로는 4*4이전의 반복이다.

소수 테이블의 경우 자기의 배수 값을 지워나가기 때문에 endNumber의 루트 값 이후는 이미 지워져 있는 상태다.

- 에라토스테네스의 채(소수테이블)

소수 테이블을 구하는 방법

N까지 정수를 배열에 입력해두고

2를 제외한 2의 배수를 지우고

3을 제외한 3의 배수를 지우고

4는 이미 지워졌으니 제끼고

5를 제외한 5의 배수를 지우고

쭉 진행하면 소수 테이블이 구현된다.

사실 ACM ICPC 예선에서 짝수가 주어지면 이는 두 소수의 합으로 나타낼 수 있는데(ex : 8의 경우 3과 5)

이를 풀기 위해서 소수테이블을 만들고 이를 이용해서 문제를 풀었었다.

이 소수테이블을 만드는 방법에 이름이 있는지는 처음 알았다...