[0x12] 수학

소수

 

소수 판정법

 

합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다.

2부터 √N까지의 수로 나누어지지 않으면 소수이다.

sqrt는 실수값으로 반환되므로 오차가 생길수 있어서 사용하지 않는게 좋기때문에 i의 루프 범위를 i*i <= n으로 잡아주면 된다.

 

범위 내에서의 소수 판정법 - 에라토스테네스의 체

vector<int> sieve(int n) {
	vector<int> primes;
	vector<bool> state(n + 1, true);
	state[1] = false; // 없어도 됨
	for (int i = 2; i <= n; ++i) {
		if (!state[i]) continue;
		for (int j = 2*i; j <= n; j += i)
			state[j] = false;
	}
	for (int i = 2; i <= n; ++i)
		if (state[i]) primes.push_back(i);
	return primes;
}

 

시간복잡도 개선안

vector<int> sieve(int n) {
	vector<int> primes;
	vector<bool> state(n + 1, true);
	state[1] = false; // 없어도 됨
	for (int i = 2; i*i <= n; ++i) {
		if (!state[i]) continue;
		for (int j = i*i; j <= n; j += i)
			state[j] = false;
	}
	for (int i = 2; i <= n; ++i)
		if (state[i]) primes.push_back(i);
	return primes;
}

 

시간복잡도는 O(NloglogN) 이다.

짤막한 팁) bool type을 vector로 사용하면 1바이트가 아닌 1비트로 저장되어 공간을 줄일 수 있다.

 

소인수 분해

 

1. N을 i로 나눌수 있으면 i로 나누어지지 않을 때 까지 i를 소인수 목록에 추가하고 N을 i로 나눈다(i >= 2)
2. i로 나누어지지 않으면 i를 증가시킨다.
3. N이 1이 될 때까지 1~2를 반복한다.

 

소인수 목록에 들어간 수는 반드시 소수이다.

위와 같은 방식의 시간복잡도는 O(N) 이지만 시간복잡도를 개선한 소수 판별법처럼 O(√N)으로 줄일 수 있다.

i의 루프 범위를 i <= N이 아닌 i*i <= N로 잡고 N이 1이 아닐 경우 그 수를 소인수 목록에 추가해주면 된다.

 

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

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

	return 0;
}

 

최대 공약수와 최소 공배수

 

약수 : 어떤 수를 나누어 떨어지게 하는 수

vector<int> divisor(int n) {
	vector<int> div;
	for (int i = 1; i * i <= n; ++i) {
		if (n % i == 0) div.push_back(i);
	}
	for (int j = (int)div.size() - 1; j >= 0; --j) {
		if (div[j] * div[j] == n) continue;
		div.push_back(n / div[j]);
	}
	return div;
}

 

시간복잡도는 O(√N) 이다.

 

최대 공약수(GCD) : 두 자연수의 공통된 약수 중 가장 큰 약수

유클리드 호제법을 이용하면 매우 빠르고 간단하게 구할 수 있다.

두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 하면 GCD(A,B) = GCD(B,r)이다.

int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b, a%b);
}

 

최소 공배수(LCM)

A×B = GCD(A,B)×LCM(A,B)

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

 

본래의 식은 (a*b) / gcd(a,b) 이지만 a,b의 값이 10^9라면 a*b는 int overflow가 발생하기 때문에 예방차원에서 계산의 순서를 바꾼 것이다.

 

연립합동방정식

 

이항계수

 

nCk = (n-1)C(k-1) + (n-1)Ck