(C언어)프로젝트 오일러(Project Euler)10. 이백만 이하 소수의 합

문제

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.

이백만(2,000,000) 이하 소수의 합은 얼마입니까?

코드

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

#define NUM 2000000

int main(void)
{
    int i, j;
    int* prime= (int*)malloc(sizeof(int) * NUM);    //배열 동적할당
    long long sum = 0;

    for (i = 2; i <= NUM+1; i++)                    //각 요소 초기화
    {
        prime[i] = i;
    }

    for (i = 2; i <= NUM; i++)
    {
        if (prime[i] == 0)                    //배열 요소가 0이면 소수가 아니므로 건너뜀
            continue;

        for (j = 2 * i; j <= NUM; j += i)    //에라토스테네스의 체 적용. 소수가 아니면 0 대입
            prime[j] = 0;
    }

    for (i = 2; i <= NUM; i++)                //소수를 모두 더한다
    {
        if (prime[i] != 0)
            sum += i;
    }

    printf("%lld", sum);

    return 0;
}

 

수가 2백만이나 되어서 효율을 위해 에라토스테네스의 체를 활용했다. 이 방식을 이해하는 데 시간이 많이 걸렸다.

​

main함수 두 번째 줄에서는 배열을 동적할당했다. 그냥 배열을 선언했더니 예외처리가 되지 않았다고 오류가 떴다. 배열 수가 너무 많아서 그런 듯하다.

​

<에라토스테네스의 체>

위키백과 참고

​

에라토스테네스의 체 자체는 이해하는 데 어려움이 없지만, 이를 프로그램으로 구현하려니 애먹었다.

 

for (i = 2; i <= NUM+1; i++);                    //각 요소 초기화
    {
        prime[i] = i;
    }​

 

첫 번째 for문을 마치면 배열은 위 상태가 된다. 인덱스에 해당하는 i를 2부터 시작했으므로 0과 1은 비워두었다.

 

for (i = 2; i <= NUM; i++)
    {
        if (prime[i] == 0)                    //배열 요소가 0이면 소수가 아니므로 건너뜀
            continue;

 

두번째 for문에서는 에라토스테네스의 체를 적용한다.

gif에서는 합성수를 색칠하는데, 프로그램에서는 0으로 초기화한다.

​

for (j = 2 * i; j <= NUM; j += i)    //에라토스테네스의 체 적용. 소수가 아니면 0 대입
            prime[j] = 0;
    }

 

두 번째 for문 안에 중첩된 for문이 실행되면

j는 4가 된다. 인덱스가 4인 배열 요소는 0이 된다. i 값이 2이기 때문에 j에다 i를 더하면 6 ,8 ,10 ... 결국 2의 배수를 모두 소거할 수 있다.

​

i가 3일 때는 3을 제외한 3의 배수가 소거된다. 4일 때는 요소가 0이므로 건너뛰고, 5로 넘어간다.

​

반복문을 마치면 소수 인덱스가 가지는 값만 살아 있게 된다.

 

for (i = 2; i <= NUM; i++)                //소수를 모두 더한다
    {
        if (prime[i] != 0)
            sum += i;
    }

 

마지막 반복문에서 요소가 0이 아닌 배열의 값, 즉 소수를 모두 sum에 더해 출력하면 끝난다.