Problem #005

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #05

◾ 1 ~ 20 모든 수로 나누어 떨어지는 가장 작은 수를 구하는 문제

 

 

---

 

 

📑 문제 풀이

// 20200120 오일러 알고리즘 Problem 05
#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n = 20;		

	while (n++)
	{
		int cnt = 0;
		for (int i = 1; i <= 20; i++)
		{
			if (n % i == 0) cnt++;
		}

		if (cnt == 20)
		{
			cout << n << "\n";
			break;
		}
	}

	return 0;
}

💬 Point

👉 오늘도 브르투포스

◾ 1씩 수를 더해간다. 이는 변수 n에 해당한다.

◾ 1부터 20까지 도는 반복문을 만든다.

◾ 해당 반복문을 통해서 n을 i로 나눈다.

◾ 만약 i로 나누어진다면 cnt에 1을 더해준다.

◾ 그 cnt가 20이 된다면 1부터 20까지의 수로 다 나누어 떨어진다는 소리.

◾ 따라서 그때 n을 반환한다.

 

 

---

 

 

But,

✅ 시간은 한 25초 정도 걸린다. 시간을 좀 더 줄일 수 있으면 좋을 것 같다.
✅ while문안에 조건문을 때려박으면 시간을 더 줄일 수 있지않을까..(?)

➕ Solution 풀이 사이트 첨수

https://www.mathblog.dk/project-euler-problem-5/

Solution to Project Euler problem 5 in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

---