10. Summation of primes

1. 개요

문제는 이곳에서 확인할 수 있다. 200만보다 작은 소수의 합을 구하는 것이 목표이다. 

소수를 찾는 데에는 에라토스테네스의 체를 이용한다. 예를 들어 2 이상 120 이하의 소수를 찾는다고 하자. 먼저 2를 남기고 2의 배수를 모두 지운다. 이후 3을 남기고 3의 배수를 모두 지운다. 다음 수인 4는 이미 지워졌으므로 5를 남기고 5의 배수를 모두 지운다. 이것을 120의 양의 제곱근보다 작은 정수 중 가장 큰 정수까지 반복하면 된다. 아래 그림^[각주:1]은 이 방법에 대한 일러스트레이션이다.

2. Ver 1.0

using System;
using System.Collections.Generic;
using System.Linq;

class ProjectEuler
{
	static void Main(string[] args)
	{
		// 에라토스테네스의 체
		List<int> seive = new List<int>();
		int lim = 2000000;
		
		seive.Add(2);
		for(int i=3; i<lim; i+=2)
		{
			seive.Add(i);
		}
		
		for(int i=3; i<=Math.Sqrt(lim); i+=2)
		{
			seive.RemoveAll(p=> p>i && p%i==0);
		}
		
		Console.WriteLine(seive.Sum(p=> Convert.ToInt64(p)));
	}
}

답은 142913828922이다.

1. 출처: 영문 위키피디아(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) [본문으로]