07
15
Programming

[C++] BOJ 20946 합성인수분해 (시행착오의 기록)

부제: 시행착오의 기록

문제 개요

20946번: 합성인수분해

합성수로 분해하자. 사전순으로 앞서는 수열로 출력해야 한다.

아이디어

  • 메모장에 쓰면서 아이디어 생각했던거.
더보기

소수 2 3 5 7 11 13 17

분해 답
4 2^2 4 (그대로)
6 2,3 6
8 2^3 8
10 2,5 10
12 2^2,3 12
14 2,7 14
15 3,5 15
16 2^4 4 4
18 2,3^2 18
20 2^2,5 20
22 2,11 22
24 2^3,3 4,6 앞에서 하나씩 묶기
25 5^2 25

28 2^2,7 28
30 2,3,5 30
32 2^5 4,8 두개 묶고 남은거 묶기
남은거 value가 1이라면 마지막거에 곱해주기

34  2,17 34
36 2^2,3^2 4 9


48 2^4,3 4 12

360 2^3,3^2,5

N 범위가 무려 $10^{12} = 1000000000000$ 까지였다^^...................

좀 쓰다 보니까 그래도 정리가 됐다.

소인수분해를 해주고 2개씩 묶어준다. 마지막에 하나가 남았으면 마지막거에 곱해준다.

대회 시간에 이거는 다 구현이 됐는데 소인수분해가 시간 안에 안 됐다...ㅎ

테스트하는데 썼던 수는

  • 2147483647 (소수)
  • 2147483649 (3*어쩌구)
  • 1073741824 (10자리)
  • 322225472

참고한 부분:

코드

  • 45%에서 시간초과 나는 코드
더보기

#include <iostream>
#include <algorithm>
#include<vector>
#include <map>
#include<ctime>
typedef long long ll;
using namespace std;

ll n;

bool isPrime(ll a) {
if (a % 2 == 0 || a == 1 || a == 9) return false;
else if (a == 2 || a == 3 || a == 5 || a == 7) return true;
if (!(a & 1)) { return false; }

ll range = a / 3;
unsigned pos = 3;
while (pos <= range) {
if (!(a % pos) || !(a % (pos + 2))) { return false; }
pos += 4;
range = a / pos;
}
return true;
}

int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

cin >> n;

clock_t start = clock();
if (isPrime(n)) { cout << "-1"; return 0; }

ll origN = n;
vector<ll> res; //소인수분해

clock_t mid1 = clock();

ll k = 2;
while (n != 1) {
if (n % k == 0) {
res.push_back(k);
n /= k;
}
else if (k == 2) {
k++;
}
else {
//while(!isPrime(k)) 
k += 2;
}
}

clock_t mid2 = clock();

ll nowN = 1;
int idx = 0;
ll tmp;
vector<ll> ans;
while (nowN < origN) {
if (idx + 1 == res.size()) { //idx위치가 마지막이다
ans.back() *= res[idx]; //마지막거에 곱해주기
nowN *= res[idx];
}
else { // idx와 idx+1을 볼 수 있다
ll tmp = res[idx] * res[idx + 1];
ans.push_back(tmp);
nowN *= tmp;
idx += 2;
}
}
printf("%0.5f\n", (float)(mid2 - mid1) / CLOCKS_PER_SEC);
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

return 0;
}

2147483649 를 넣으면 소인수분해하는데 2.46초가 걸린다ㅎㅎ;

솔루션에

라는 말이 있어서 여기에서 아이디어를 얻어서 코드를 고쳐보았다.

소인수분해 하는 부분만 고침.

더보기

#include <iostram>
#include <algorithm>
#include<vector>
#include <map>
#include<ctime>
typedef long long ll;
using namespace std;

ll n;

bool isPrime(ll a) {
if (a % 2 == 0 || a == 1 || a == 9) return false;
else if (a == 2 || a == 3 || a == 5 || a == 7) return true;
if (!(a & 1)) { return false; }
ll range = a / 3;
unsigned pos = 3;
while (pos <= range) {
if (!(a % pos) || !(a % (pos + 2))) { return false; }
pos += 4;
range = a / pos;
}
return true;
}

int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

cin >> n;

clock_t start = clock();
if (isPrime(n)) { cout << "-1"; return 0; }

ll origN = n;
vector<ll> res; //소인수분해

clock_t mid1 = clock();

ll k = 2;
while (n != 1) {
if (isPrime(n)) {
res.push_back(n);
n /= n;
break;
}
else if (n % k == 0) {
res.push_back(k);
n /= k;
}
else if (k == 2) {
k++;
}
else {
k += 2;
}
}
for (int i = 0; i < res.size(); i++) cout << res[i] << " ";

clock_t mid2 = clock();

ll nowN = 1;
int idx = 0;
ll tmp;
vector<ll> ans;

while (nowN < origN) {
if (idx + 1 == res.size()) { //idx위치가 마지막이다
ans.back() *= res[idx]; //마지막거에 곱해주기
nowN *= res[idx];
}
else { // idx와 idx+1을 볼 수 있다
ll tmp = res[idx] * res[idx + 1];
ans.push_back(tmp);
nowN *= tmp;
idx += 2;
}
}
printf("%0.5f\n", (float)(mid2 - mid1) / CLOCKS_PER_SEC);
for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

return 0;
}

소인수분해 하는 방법을 조금 바꿨다.

이 코드에 2147483649 를 넣으면 소인수분해하는데 0.001초가 걸린다..........ㅎ.........................
애초에 2147483649는 $3*715827883$ 인데,
3을 나누고 나서 나머지가 소수인데 이걸 k += 2 하면서 3에서 715827883까지 더하고 앉아있으니까 시간초과가 나는거였다............................................................ㅋ...ㅋㅋㅋㅋ............
isPrime() 이 빠르다고 생각해서 짰다. 2147483649가 소수인지 판단하는데 0.001초가 걸렸으니까 별 부담이 안 갔다고 생각했는데...

그래서 또 중간 코드.

  • 7%에서 시간 초과.
#include <iostream>
#include <algorithm>
#include<vector>
#include <map>
#include<ctime>
typedef long long ll;
using namespace std;

ll n;

bool isPrime(ll a) {
	if (a % 2 == 0 || a == 1 || a == 9) return false;
	else if (a == 2 || a == 3 || a == 5 || a == 7) return true;
	if (!(a & 1)) { return false; }

	ll range = a / 3;
	unsigned pos = 3;
	while (pos <= range) {
		if (!(a % pos) || !(a % (pos + 2))) { return false; }
		pos += 4;
		range = a / pos;
	}
	return true;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	
	clock_t start = clock();
	if (isPrime(n)) { 
		cout << "-1"; 
//		clock_t afterprime = clock();
//		printf("%0.5f\n", (float)(afterprime - start) / CLOCKS_PER_SEC);
		return 0; 
	}

	ll origN = n;
	vector<ll> res; //소인수분해
	
//	clock_t mid1 = clock();

	ll k = 2;
	while (n != 1) {
		if (isPrime(n)) {
			res.push_back(n);
			n /= n;
			break;
		}
		else if (n % k == 0) {
			res.push_back(k);
			n /= k;
		}
		else if (k == 2) {
			k++;
		}
		else {
				k += 2;
		}
	}
//	for (int i = 0; i < res.size(); i++) cout << res[i] << " ";

//	clock_t mid2 = clock();

	ll nowN = 1;
	int idx = 0;
	ll tmp;
	vector<ll> ans;

	while (nowN < origN) {
		if (idx + 1 == res.size()) { //idx위치가 마지막이다
			ans.back() *= res[idx]; //마지막거에 곱해주기
			nowN *= res[idx];
		}
		else { // idx와 idx+1을 볼 수 있다
			ll tmp = res[idx] * res[idx + 1];
			ans.push_back(tmp);
			nowN *= tmp;
			idx += 2;
		}
	}
//	printf("%0.5f\n", (float)(mid2 - mid1) / CLOCKS_PER_SEC);
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

	return 0;
}

를 슬랙에 올렸더니

N이 소수인지 확인할때는 sqrt(N) 까지만 나누어 떨어지는지 체크해도 충분합니다. 위코드는 k를 N(10의 12승)까지 전부 다 확인하고, isprime이라는 함수도 작동하므로 시간이 오래걸립니다.

라는 조언을 해주셨다.

isPrime이 빠르다고 생각했는데 0.001초가 $10^{12}$번 쌓이면 $10^9$초가 되니까 시간이 오래걸리는거였다.

그래서

k*k <= origN 을 추가했다

N의 소인수는 (소수인 경우를 제외하고) $sqrt(N)$만에 찾을수있다!!!!!!!!!!!!!! 왜냐!!!!!!!! 나누면 되니까~!!!!!!!!!!!!!!

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
typedef long long ll;
using namespace std;

ll n;

bool isPrime(ll a) {
	if (a % 2 == 0 || a == 1 || a == 9) return false;
	else if (a == 2 || a == 3 || a == 5 || a == 7) return true;
	if (!(a & 1)) { return false; }
	ll range = a / 3;
	unsigned pos = 3;
	while (pos <= range) {
		if (!(a % pos) || !(a % (pos + 2))) { return false; }
		pos += 4;
		range = a / pos;
	}
	return true;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	
	clock_t start = clock();
	if (isPrime(n)) { cout << "-1"; return 0; }

	ll origN = n;
	vector<ll> res; //소인수분해


	if (origN == 4) { //아래코드에서 런타임에러남;
		cout << 4;
		return 0;
	}

	ll k = 2;
	while (n != 1 && k*k <= origN) {
		if (n % k == 0) {
			res.push_back(k);
			n /= k;
		}
		else if (k == 2) {
			k++;
		}
		else {
			k += 2;
		}
	}
	
	if(n != 1 && isPrime(n)) 
		res.push_back(n); //위에 k*k<=N 제한으로 미처 다 못 넣은 경우

	// printf("n:%lld, k:%lld\n", n, k);
	 for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
	 cout << "\n";

	ll nowN = 1;
	int idx = 0;
	vector<ll> ans;

	while (nowN < origN) {
		if (idx + 1 == res.size()) { // idx위치가 마지막이다
			ans.back() *= res[idx]; // 마지막거에 곱해주기
			nowN *= res[idx];
		}
		else { // idx와 idx+1을 볼 수 있다
			ll tmp = res[idx] * res[idx + 1];
			ans.push_back(tmp);
			nowN *= tmp;
			idx += 2;
		}
	}

	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	return 0;
}

근데 100% 까지 올라가더니 런타임에러가 나는거다....... 미치고환장할노릇.

위 코드의 문제점은 무엇이었을까? 를 생각하며 소인수분해를 겁나게 뒤졌다.

근데 문제는 다른곳에 잇었다.

n이 2인 경우에 런타임 에러가 발생합니다. isprime함수 내에서 a가 짝수인 경우를 먼저 확인해서 a가 2인 경우에 false를 반환해버립니다. if문과 else if문의 순서를 바꾸면 될 것 같습니다!
(슬랙에서 받은 조언)

ㅋㅋㅋㅋㅋㅋㅋㅋ처음에 isPrime 함수를 잘못짰던것.....! 2는 소수인데..!

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
typedef long long ll;
using namespace std;

ll n;

bool isPrime(ll a) {
	if (a == 2 || a == 3 || a == 5 || a == 7) return true;
	if (a % 2 == 0 || a == 1 || a == 9) return false;
	if (!(a & 1)) { return false; }
	ll range = a / 3;
	unsigned pos = 3;
	while (pos <= range) {
		if (!(a % pos) || !(a % (pos + 2))) { return false; }
		pos += 4;
		range = a / pos;
	}
	return true;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	
	clock_t start = clock();
	if (isPrime(n)) { cout << "-1"; return 0; }

	ll origN = n;
	vector<ll> res; //소인수분해


	if (origN == 4) { //아래코드에서 런타임에러남;
		cout << 4;
		return 0;
	}

	ll k = 2;
	while (n != 1 && k*k <= origN) {
		if (n % k == 0) {
			res.push_back(k);
			n /= k;
		}
		else if (k == 2) {
			k++;
		}
		else {
			k += 2;
		}
	}
	
	if(n != 1 && isPrime(n)) 
		res.push_back(n); //위에 k*k<=N 제한으로 미처 다 못 넣은 경우

	// printf("n:%lld, k:%lld\n", n, k);
	// for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
	// cout << "\n";

	ll nowN = 1;
	int idx = 0;
	vector<ll> ans;

	while (nowN < origN) {
		if (res.size() == 1) {
			ans.push_back(res[0]);
			nowN *= res[0];
		}
		if (idx + 1 == res.size()) { // idx위치가 마지막이다
			ans.back() *= res[idx]; // 마지막거에 곱해주기
			nowN *= res[idx];
		}
		else { // idx와 idx+1을 볼 수 있다
			ll tmp = res[idx] * res[idx + 1];
			ans.push_back(tmp);
			nowN *= tmp;
			idx += 2;
		}
	}

	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	return 0;
}

교훈: 작은 것부터 돌아보자

끝

진짜 허무했다 ㅜㅜㅋㅋㅋㅋㅋㅋㅋㅋㅋ엄청 매달렸던 문제.

이 카테고리의 다른 글

2021.07.19
[C++] BOJ 1032 명령 프롬포트

2021.07.19
[C++] BOJ 1550 : 16진수

2021.06.29
[C++] BOJ 10546 _ 맵 사용 연습

2021.01.07
[C++] BOJ 2847 게임을 만든 동준이

COMMENT
 

티스토리툴바