백준 16563번 어려운 소인수 분해 문제와 내 오개념

https://www.acmicpc.net/problem/16563

백준 16563번 어려운 소인수 분해 문제이다.

2018년 서강대학교 교내 프로그래밍 경시대회 Master등급, 4학기 이하 학생만 참여하는 대회 문제라길래

한번 재미로 문제를 풀어봤다가 빤쓰런각 ㅠㅠ

문제를 보고, 에라토스테네스의 채를 이용해서 소수를 다 구한 뒤, 소수들 리스트로 소인수 분해를 하면 되겠다 생각했었다.

근데 이 문제에서 소인수 분해하는 수의 개수가 꽤 많다는 점이, 내가 에라토스테네스의 채를 제대로 이해하지 못하고 있다는 것을 알게 해 주었다 ㅠ

문제 분석

말 그대로 소인수 분해를 하면 된다. 다만 소인수 분해를 하는 횟수와, 수의 크기가 꽤 되기 때문에, 소수들을 일일이 하나씩 구하다가는 TLE가 나기 십상이다.

500만이라는 수 보다 작은 소수들을 빠르게 한번 다 구해버린 뒤 (전처리 과정), 소인수 분해를 차차착 해주면 되는데

이정도 범위는 배열로 메모리를 잡을 수 있으므로, 에라토스테네스의 채를 이용하면 좋다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

내가 조금 잘못 알고 있던 개념

사실 완전히 잘못 알고 있던 것은 아니고, 에라토스테네스의 채에서 어느정도 스킵하고 지나가야 하는 부분도, 잘 못 믿고 더블체크를 하는 과정이 항상 있었다.

이 과정에서 조금 비효율적이었지만, 크게 상관은 없는 그런.. 상황이었다.

에라토스테네스의 채는 알려진 소수를 하나 알게 되면, 그 소수의 배수들을 모조리 없애버리는 소거식으로 한 뒤, 남은 수들은 소수라고 보는 방식이다.

N=500만, 인 상황에서 N보다 작은 모든 소수를 구해야 하는 상황이다.

기존에 내가 잘못 알고 있던 부분은 2부터 시작해서 채에 걸러지지 않은 녀석들이 소수가 맞는지 2부터 sqrt(n)까지의 수로 다시 나누어서 확인하고 있었는데, 이 부분 때문에 TLE가 많이 났다.

2부터 이미 채에 걸러지지 않았다면, 그냥 소수가 맞다고 보면 된다.

왜 그런가 하면..

//(N//)이하의 소수를 다 구한다고 하면, //(\sqrt{N}//)이하의 소수의 배수들을 다 소거했을 때, //([\sqrt{N}, N]//) 범위에 있는 걸러지지 않은 모든 수는 소수가 맞다.

왜 그런가 하면 귀류법으로 증명이 가능하다.

만약 //([\sqrt{N}, N]//)사이에 걸러지지 않았지만, 소수가 아닌 합성수가 존재한다고 가정해 보자.

이 수를 K라고 하겠다.

이 수는 합성수이므로 //(K=p*q//)로 인수분해가 가능할 것이다. //(p, q//)는 소수 일 수도 있고 아닐 수도 있다.

어쨋든 이 사실로 인하여, //(min(p, q) <= \sqrt{N}//)라는 사실이 성립한다. 그렇다는 것은 //(p//)나 //(q//)중 하나의 수는

소수의 배수들을 소거할 때 무조건 한번은 출연을 했다는 것이다. 

//(p//)나 //(q//)중 작은 수가 합성수라면, 이미 그 보다 작은 소수의 배수로서 등장을 했을 것이고, 소수라고 하더라도

모든 소수가 다 걸러졌기 때문에 걸려졌을 것이다.

그러므로, 해당 범위 //([\sqrt{N}, N]//)에는 합성수가 남아있을 수 없다.

뭐 이런 결론이 된다.

" //(\sqrt{N}//)이하의 소수의 배수들을 다 소거했을 때," 이 사실이 참이라면 성립하게 된다.

이런식으로 Inductive step이 성립하게 되었으니, 수학적 귀납법으로도 확장이 가능할 것으로 보인다.

뭐 그래서 맞을 것이다. 

맞겟지 아마 증명이?

틀린 부분이 있다면 얼마든지 지적, 조언 등 환영합니다.

그래서 제곱근까지의 소수로만 확장시켜도 그 위도 다 소수가 남아있는게 맞다고 합니다.

그리고 소수를 찾아서 그 배수들을 소거할 때, 만약 소수 //(p//)를 찾았다면 다음 첫 소거 아이템은 //(p^2//)부터 시작해도 된다고 한다.

이미 그 이전 것들은 즉, //(p, p*2, p*3, ... , p*(p-1)//)는 다 소거가 되었다고 볼 수 있다. 오른쪽에 붙는 //([1, p-1]//)에 해당하는 수 들은

소수이면 이미 다 체크되었고, 합성수라면 또 어느 소수의 배수로 다 체크되었기 때문에 다 걸려있다 이말입니다. ㅠ

하 이 부분을 제대로 짚고 공부하지 않아서 이렇게 빵꾸가 나버린 논리 ㅠ

고로 구현한 코드는..

그런점을 이용하면 소수를 쉽게 구할 수 있다.

그리고 채를 bool 배열로만 잡았었는데, int로 잡아서 다음과 같게도 구현이 가능하더라..

int배열에 들어가는 값은, int arr[i]라 하면 i가 갖는 가장 작은 소인수 값이 해당 배열에 들어가게 하면 쉽~게 소인수 분해를 하도록 만들 수 있다더라 ㅠ

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

int min_factor[5000005];
void solve(int n) {
	while (n > 1) {
		printf("%d ", min_factor[n]);
		n /= min_factor[n];
	}
	putchar('\n');
}
int main() {
	min_factor[0] = min_factor[1] = -1;
	for (int i = 2; i <= 5000000; i++) {
		min_factor[i] = i;
	}

	for (int v = 2; v * v <= 5000000; v++) {
		if (min_factor[v] == v) { //v가 소수라면
			for (int k = v * v; k <= 5000000; k += v) {
				if (min_factor[k] == k)
					min_factor[k] = v;
			}
		}
	}
	
	int n;
	scanf("%d", &n);
	while (n--) {
		int v;
		scanf("%d", &v);
		solve(v);
	}
	return 0;
}

하하 반성합시다~

하나라도 제대로 이해하면서 공부해야 합니다~ ㅠㅠ