소인수 분해, 약수의 개수, 오일러 피함수

에라토스테네스 :https://suuntree.tistory.com/36?category=805933

 

소인수분해 자체로는 문제가 많이 나오지않지만 오일러 피함수는 알고있어야 한다.

 

1. 소인수분해 : O(loglogn) -> while문 수행횟수 log, while문에서 n의 범위를 줄여줌

n이 소수가 아니라면, n은 루트n 이하의 소인수를 갖는다. i==2부터 차례대로 n을 나눌 수 있다면 i로 n을 더이상 나눌 수 없을 때까지 나누면서 진행한다. 과정이 끝나면 n=1 또는 n=소수가 된다.

 

 

<코드>

ll n; cin >> n;
vector<P> p;
for (ll i = 2; i * i <= n; i++) {
	if (n % i == 0) {
		ll cnt = 0;
		while (n % i == 0) {	//이 부분을 로그시간으로 최적화할 수 있지않을까?
			n /= i;
			cnt++;
		}
		p.push_back({ i, cnt });
	}
}
//n이 소수인 경우
if (n != 1) {
	p.push_back({ n,1 });
}

for (P pp : p) {
	cout << pp.first << " ^ " << pp.second << '\n';
}

 

<결과>

<+ 약수의 개수함수>

위 p배열의 second들을 1더해서 다 곱해주면 된다.

---

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

https://codeforces.com/contest/1295/problem/D

 

2. 오일러 피함수

n이하의 정수 중 n과 서로소인 정수의 개수를 반환하는 함수.

수식1

p는 n의 i번째 소인수를 의미, ai는 pi의 제곱수이다. k는 n의 소인수 개수이다.

 

수식2

수식2의 변형으로 피함수를 구할 수 있다. n에 모든 소인수 pi를 나눠주고  (pi-1)을 곱해주면 된다.

 

다시말해서 다음 수식을 구현해주기만 하면 된다.

<코드>

ll n; cin >> n;
ll phi = n;
for (ll i = 2; i * i <= n; i++) {
	if (n % i == 0) {
		phi /= i;
		phi *= (i - 1);
	}
	while (n % i == 0) n /= i;
}
if (n != 1) {
	phi /= n;
	phi *= (n - 1);
}
cout << phi << '\n';