오일러 프로젝트 10번

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

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

소수 구하는 범위가 너무 커서 처음 짠 코드는 10분이 넘어가도 구하지 못했다.

그래서 검색 결과 에라토스테네스의 체 방식을 사용하여 소스 코드를 구성해 보았다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

자세한 내용은 위의 링크를 참고하면 된다.

#include <stdio.h>

#include <stdbool.h>

void eratos(int n){

bool PrimeArray[n+1];

int i,j;

long long sum = 0;

if(n<=1) return;

for(i=2; i<=n ; i++)

PrimeArray[i] = true;

for(i=2; (i*i) <= n; i++){

if(PrimeArray[i]){

for(j=i*i; j<=n; j +=i)

PrimeArray[j] = false;

}

}

for(i=2; i<=n ; i++){

if(PrimeArray[i] == true)

sum = sum + i;

}

printf("%lld\n",sum );

}

int main (void){

int n;

printf("구하려는 소수의 범위를 정하시오 \n");

scanf("%d",&n);

eratos(n);

return 0;

}