Problem #003

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #03

소인수분해 : 어떤 수를 소수의 곱으로만 나타내는 것
ex) 8 = 2 x 2 x 2

소인수 : 소인수분해의 소수들

◾ 특정 수의 가장 큰 소인수를 구하는 문제

◾ 소인수분해로 나타내서 그중에서 가장 큰 값을 구하면 되는 문제

 

 

---

 

 

📑 문제 풀이

//20200108오일러 알고리즘 Problem 3
#define _CRT_NO_WARNINGS
#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;				//소인수 분해 할 피수
	int ans = 0;		//제일 큰 수가 저장될 출력 변수
	int cnt = 0;		//소수인지 확인할 때 쓰는 cnt 변수

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cnt = 0;
		for (int j = 1; j <= i; j++)
		{
			//printf("i: %d, j: %d\n", i, j);
			if (i % j == 0) {
				cnt++;
				//cout << "cnt : " << cnt << "\n\n";

			}
		}

		if (cnt == 2 && N % i == 0)
		{
			ans = i;
			//cout <<"ans : " << ans << endl;
		}
	}

	cout << "\n" << "ans : " << ans << endl;
	return 0;
}

◾ 첫번째 풀이, 풀지 못했다 😥

◾ 위처럼 코드를 짜면 반복문이 두번 돌아서 O(N^2)이 된다.

◾ 이렇게 되면 큰수를 넣게 되면 시간이 무척 오래걸린다.

◾ 풀지 못해 슬프군

 

 

---

 

 

So,

✅ 넣을 값을 정할때도 저렇게 큰 값이라면 int가 아닌 long 아니면 long long 값으로 넣기
✅ 값이 반복문을 돌면서 나뉘어지면, 그 값으로 또 나누어 반복문을 돌게 하는 방법으로 풀 것
✅ 소인수 문제가 나오면 count를 세지말고 윗 방법을 기억할 것

➕ Solution 풀이 사이트 첨부

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

Solution to Project Euler problem 3 in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

 

---