Problem #010

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #10

◾ 200만 이하의 소수의 합을 구하는 문제

소수란?
1과 자기자신으로 밖에 나누어지지 않는 수

 

 

---

 

 

📑 문제 풀이

✅ 에라토스테네스의 체

#include <iostream>
#define MAX 2000000
using namespace std;

bool check[MAX + 1];

int main()
{
	for (int i = 2; i * i <= MAX; i++)
	{
		if (check[i] == false)
		{
			for (int j = i * i; j <= MAX; j += i)
				check[j] = true;
		}
	}

	long long sum = 0;

	for (int i = 2; i <= MAX; i++)
	{
		if (check[i] == false)
			sum += i;
	}

	cout << sum << "\n";

	return 0;
}

💬 Point

👉 소수문제는 에라토스테네스의 체로 쉽게 풀 수 있다.

◾ 아예 외워서 사용하는 것을 추천한다. (물론 필자는 항상 까먹음)

◾ memoization의 방법을 사용한다.

• 이는 방문을 기록하는 memo 용도의 배열을 두는 것을 이른다.
• 본 코드에서 check[] 배열이 이에 해당한다.

◾ 에라토스테네스의 체는 우선적으로 MAX의 수 이하만큼의 수를 돌면서 모든 배수들을 없애는 것에 기초한다.

◾ 2의 배수를 지우고, 3의 배수를 지우고 .. 이러는 형식.

◾ 그렇게 해서 지운 것들을 memoization 변수에 표시를 한다.

• 본 코드에서는 true로 표시하였다.
• 근데 1로 표시하는걸 추천

◾ 이렇게 배수를 지우고 나면 소수들만 남는다.

◾ 해당 소수들을 더해주는 것이다.

---

✅ 다른 풀이

#include <iostream>
#define MAX 2000000
using namespace std;

bool prime(int n)
{
	if (n < 2) return false;
	
	for (int i = 2; i*i <= n; i++)
	{
		if (n % i == 0) return false;
	}

	return true;
}

int main()
{
	long long int sum = 0;
	for (int i = 2; i <= MAX; i++)
	{
		if (prime(i)==true)
		{
			sum += i;
		}
	}
	
	cout << sum << "\n";

}

◾ prime이라는 함수를 만들어줘서 소수인지 아닌지 판별한다.

◾ 만약 해당 수가 소수가 아니라면 false를 반환하고 소수라면 true를 반환한다.

◾ prime 함수는 해당 수만큼 반복문을 돈다.

 

 

---

 

 

But,

✅ 처음에 sum 변수를 int로 잡는 실수를 범함.
✅ 그래서 계속 답이 안구해졌다.
✅ 이렇듯, 자릿수 범위를 잘못 두는 실수를 하지 않도록 아예 long long으로 둘 것.
✅ 근데 check 변수 200만개인거 실화

➕ 풀이 사이트 첨부

https://www.mathblog.dk/sum-of-all-primes-below-2000000-problem-10/

Solution to Project Euler problem 10 in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

---