소수

소수 판정

N보다 작은 수를 모두 순회

1과 자기자신인 N 사이의 수를 순회하면서 나눠지는 수가 있으면 소수가 아니고, 없으면 소수라고 판단하는 방법
2부터 N-1까지의 수를 순회하므로 시간복잡도는 O(N)이다.

bool is_prime(int x) {
  for (int i = 2; i < x; i++){
    if (x % i == 0)
      return false;
  }
  return true;
}

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

N의 약수 중에서 1을 제외한 가장 작은 수를 x라고 가정하면, N/x은 N의 약수 중의 하나일 것이다.
그런데 x가 N의 약수 중에서 가장 작은 수이므로 N/x >= x 라는 수식이 성립할 것이다. 여기서 양변에 x를 곲하면 N >= x * x 라는 수식이 성립한다.
따라서 x만큼의 수까지만 나눠서 소수를 판별할 수 있으므로 해당 방법의 시간복잡도는 O(√N)이다.

bool is_prime(int x) {
  for (int i = 2; i*i <= x; i++){
    if (x % i == 0)
      return false;
  }
  return true;
}

범위 내의 소수 찾기

에라토스테네스의 체

2부터 N까지 2의 배수, 3의 배수, ... N의 배수를 모두 지워나가면 지워지지 않은 수는 소수라는 것을 판단할 수 있다.
에라토스테네스의 체를 이용하면 범위 내의 소수를 모두 찾아내기에는 위의 방식들을 이용하는 것보다 더 효율적이다.
에라토스테네스의 체를 활용한 방식으로 정해진 수의 범위에서 소수를 찾아서 반환하는 코드는 다음과 같다.

vector<int> get_primes(int x) {
  vector<int> primes;
  vector<bool> state(x+1, true);
  for (int i = 2; i * i <= x; i++){
    if (!state[i])
      continue;
    for (int j = i; j <= x; j += i)
      state[j] = false;
  }
  for (int i = 2; i <= x; i++){
    if (state[i])
      primes.push_back(i);
  }
  return primes;
}

에라토스테네스의 체를 활용한 코드 최적화

주어진 범위가 30이고 2, 3, 4의 배수를 모두 지웠으며 5에 대한 배수를 지우려고 하는 경우를 생각해보자.
이미 2, 3, 4의 배수가 지워졌으므로 2x5, 3x5, 4x5에 해당하는 수는 지워졌을 것이다. 즉, 5보다 더 작은 수와 곱해진 합성수는 이미 지워진 것이다. 따라서 5의 배수를 지울 때에는 5x5에 해당하는 수부터 더 높은 수와 곱해진 5의 배수만을 지우면 된다는 것이다.
이를 적용한 코드는 다음과 같으며 시간복잡도는 O(√N)이다.

vector<int> get_primes(int x) {
  vector<int> primes;
  vector<bool> state(x+1, true);
  for (int i = 2; i * i <= x; i++){
    if (!state[i])
      continue;
    for (int j = i * i; j <= x; j += i)
      state[j] = false;
  }
  for (int i = 2; i <= x; i++){
    if (state[i])
      primes.push_back(i);
  }
  return primes;
}

최대공약수

약수 구하기

어떤 수를 나눌 수 있는 수가 약수이다.
따라서 N이라는 수가 있으면 N까지 전부 순회할 필요없고, N의 제곱근 이전까지의 약수만 알면 그 약수의 몫이 또 다른 약수라는 것을 알 수 있다. 따라서 약수를 구하는 시간복잡도는 O(√N) 이다.

vector<int> divisors(int N) {
	vector<int> divs;
	for (int i = 1; i * i <= N; i++) { // 제곱근 이전의 약수 구하기
		if (N % i == 0)
			divs.push_back(i);
	}
	for (int i = divs.size() - 1; i >= 0; i--) { //이미 구해둔 약수의 몫
		if (divs[i] * divs[i] == N)
			continue;
		divs.push_back(N / divs[i]);
	}
	return divs;
}

유클리드 호제법

A를 B로 나눈 나머지가 r이면 GCD(A,B) = GCD(B, r) 이다.

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

연립합동방정식

중국인의 나머지 정리?
https://schbeom.tistory.com/366

이항계수

n개 중에서 k개를 순서 생각하지 않고 뽑는 경우의 수를 구할 수 있다

식 그대로 다음과 같이 구현 가능하다.

int comb(int N, int K) {
	int result = 1;
	for (int i = 1; i <= N; i++)
		result *= i;
	for (int i = 1; i <= K; i++)
		result /= i;
	for (int i = 1; i <= N - K; i++)
		result /= i;
	return (result);
}

하지만 n과 k가 커지는 경우에는 수가 너무 커지는 문제가 발생한다.
이런 문제를 이항계수의 성질을 활용하여 해결할 수 있다.

• 특정한 A가 선택되지 않는 경우 : A를 제외한 n-1개 중에서 k개를 선택하는 경우 -> $\binom{n-1}{k}$
• 특정한 A가 선택되는 경우 : A를 제외한 n-1개 중에서 A가 뽑히는 횟수 중에 하나를 뺀 k-1개를 선택하는 경우 -> $\binom{n-1}{k-1}$

해당 성질을 이용하여 DP로 문제를 해결할 수 있다.
앞서 설명한 방법으로 11051 - 이항계수 문제를 풀면 다음과 같다.

#include <iostream>
using namespace std;

int main(int argc, char **argv) {
	int N, K;
    int comb[1001][1001];
	cin >> N >> K;
	comb[0][0] = 1;
	for (int i = 1; i <= N; i++) {
		comb[i][0] = 1;
		for (int j = 1; j <= K; j++) {
			comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % 10007;
		}
	}
	cout << comb[N][K];
	return (0);
}