정수론 - 소수 판정, 에라토스테네스의 체, 유클리드 호제법

소수 판정

소수는 1 또는 자기 자신 이외에는 나누어떨어지지 않는 수이다. 따라서 어떤 수 N이 소수인지 판단하기 위해서는 N을 2 이상 \(\left \lfloor \sqrt{N} \right \rfloor\) 이하의 수로 나누어 떨어지는지 확인하면 된다. 이때 1은 예외 처리해 주어야 한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

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

	int N;
	cin >> N;

	bool prime{true};

	if (N == 1)
		prime = false;
	for (int i{2}; i * i <= N; i++)
	{
		if (N % i == 0)
		{
			prime = false;
			break;
		}
	}

	if (prime)
		cout << N << " is the prime number\n";
	else
		cout << N << " is not the prime number\n";
}

이때의 시간복잡도는 \( O(\sqrt{N}) \)이다.

 

 

에라토스테네스의 체

N 이하의 정수 x가 소수인지 판별하는 알고리즘

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N;
bool sieve[101]; // false면 소수, true면 소수가 아님

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

	cin >> N;
	sieve[1] = true;
	for (int i{2}; i <= N; i++)
	{
		if (sieve[i]) // 소수가 아니면 무시
			continue;

		for (int j{i * 2}; j <= N; j += i)
			sieve[j] = true;
		// 소수의 배수를 전부 걸러낸다.
	}
}

시간복잡도는 \( O(  N log logN )\)이다.

 

 

유클리드 호제법

두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘

두 수의 최대공약수는 두 수 중 작은 수와 두 수의 나머지의 최대공약수와 같다는 것을 이용한 알고리즘이다.

 

두 양의 정수 \(A\), \(B\)가 존재하고,  \(A \geq B\)이며, 두 수의 최대공약수는 \(G\)라 하자. 그렇다면 다음 식이 성립한다.

$$ 1. A = Ga, B = Gb (a, b는 서로소) $$

$$ 2. A = Bq + r (q = A / B, r = A mod B) $$

1번 식에 의해 2번 식은 다음과 같이 변형된다.

$$ Ga = Gbq + r $$

$$ G(a - bq) = r $$

\(a - bq = x\)라 할 때, 

$$ r = Gx $$

\(B\)와 \(r\)은 모두 공통인수 \(G\)를 가지므로,  \(B\)의 인수 \(b\)와 \(r\)의 인수 \(x\)가 서로소임을 증명하면 \(G\)가 최대공약수임을 알아낼 수 있다.

만일 \(b\)와 \(x\)가 서로소가 아니라면,

$$ x = a - bq = tm $$

$$ b = tn $$

$$ 즉, a - bq = a - tnq = tm, a = t(nq - m) $$

그런데 \(a\)와 \(b\)는 서로소인데 현재 \(t\)라는 공통인수를 가지므로, 가정은 모순이다.

따라서 \(b\)와 \(x\)가 서로소이며, \(B\)와 \(r\)의 공통인수 \(G\)는 최대공약수이다.

 

즉, 두 양의 정수  \(A\), \(B\)의 최대공약수를 구하는 함수  \(gcd(A, B)\)는

$$ gcd(A, B) = gcd(B, r) = gcd(B, A mod B) $$

라 쓸 수 있다.

 

두 수가 매우 크다면 공식을 한 번만 적용해서는 최대공약수를 알아내기 어려우므로, B가 0이 될 때까지 해당 공식을 적용하면 A가 곧 최대공약수이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int gcd(int A, int B)
{
	if (B == 0)
		return A;
	return gcd(B, A % B);
}

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

	int A, B;
	cin >> A >> B;
	cout << gcd(A, B);
}

 

c++에는 이를 더 간편하게 구하기 위해 최대공약수, 최소공배수를 구하는 method, gcd와 lcm이 존재한다. 최대공약수를 구하고자 하는 두 수를 method의 인자에 넣으면 간편하게 최대공약수를 구할 수 있다. 최소공배수도 마찬가지이다.

헤더 파일 : <numeric>

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

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

    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << " " << lcm(a, b) << "\n";
}

https://en.cppreference.com/w/cpp/numeric/gcd

std::gcd - cppreference.com

 

시간복잡도는 \(A > B\)일 때 \(O(log B)\)이다. 자세한 설명은 아래 링크에 있다.

https://en.wikipedia.org/wiki/Euclidean_algorithm#Worst-case

Euclidean algorithm - Wikipedia