[Do it! 알고리즘 코딩테스트: Chapter 7. 정수론] 소수 구하기(Finding Prime Numbers), 오일러 피(Euler's phi)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

7- 1. 소수 구하기

 

 소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.

 

 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체(Sieve of Eratosthenes)가 있다. 

 

Sieve of Eratosthenes Alogirthm

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.

3. 배열의 끝까지 과정 2를 반복한 후 배열에 남은 모든 수를 출력한다.

 

 

 

// Baekjoon Online Judge Problem. 1929

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int M, N;
	cin >> M >> N;

	vector<int> prime_number(N + 1, 0);

	for (int i = 1; i < N + 1; i++)
		prime_number[i] = i;


	for (int i = 2; i < N + 1; i++) {
		
		if (prime_number[i] == -1)
			continue;

		for (int j = 2; j < (N / i) + 1; j++) {
			prime_number[i * j] = -1;
		}
	}

	for (int i = M; i < N + 1; i++) {
		if (prime_number[i] == -1)
			continue;
		else
			if (i == 1)
				continue;
			cout << prime_number[i] << '\n';
	}

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1456

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long A, B;
	cin >> A >> B;

	vector<long long> prime_number(sqrt(B) + 1);
	vector<long long> almost_prime;

	for (long long i = 2; i <= sqrt(B); i++)
		prime_number[i] = i;


	for (long long i = 2; i <= sqrt(B); i++) {

		if (prime_number[i] == -1)
			continue;

		for (long long j = i + i; j <= sqrt(B); j = j + i) {
			prime_number[j] = -1;
		}
	}

	for (long long i = 2; i <= sqrt(B); i++) {
		if (prime_number[i] == -1)
			continue;

		almost_prime.push_back(i);
	}

	long long count = 0;

	for (long long prime : almost_prime) {
		long long power = prime * prime;

		while (power <= B) {
			if (A <= power)
				count += 1;

			if (power > B / prime) // overflow avoid
				break;

			power *= prime;
		}
	}

	cout << count;

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1747

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	vector<int> prime(1000001, 0);
	cin >> N;

	for (int i = 1; i < 1000001; i++)
		prime[i] = i;

	int answer = 1003001;

	for (int i = 2; i < sqrt(1000001); i++) {

		if (prime[i] == -1)
			continue;

		for (int j = i + i; j < 1000001; j = j + i) { 
			prime[j] = -1;
		}
	}

	for (int i = 2; i < 1000001; i++) {
		if (prime[i] != -1) {

			string str = to_string(i);
			string reverse_str = str;
			reverse(reverse_str.begin(), reverse_str.end());

			if (str != reverse_str || i < N)
				continue;

			answer = i;
			break;
		}
	}

	cout << answer;

	return 0;
}

 

 

// Baekjoon Online Judge Problem. 1016

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long min, max;
	cin >> min >> max;
	vector<bool> prime(max - min + 1, false);

	for (long i = 2; i <= sqrt(max); i++) {

		long square = i * i;
		long start = min / square;

		if (min % square != 0)
			start++;

		for (long j = start * square; j < max + 1; j += square) {

			if (j >= min)
				prime[j - min] = true;
		}
	}

	int count = 0;

	for (int i = 0; i < max - min + 1; i++) {
		if (!prime[i])
			count++;
	}

	cout << count;

	return 0;
}

 

 

7- 2. 오일러 피(Euler's phi)

 

오일러 피 함수(ϕ(n), Euler’s Totient Function)는 1부터 n까지의 정수 중에서 n과 서로소(Coprime)인 수의 개수를 반환하는 함수다. 즉, gcd(x, n) = 1을 만족하는 x(1 ≤ x ≤ n)의 개수를 구하는 함수다.

 

 

오일러 피 함수 공식

소인수분해를 이용하면, 다음과 같은 공식을 사용할 수 있다.

여기서,

• p 는 n 의 소인수 (prime factor).
• p∣n​ 는 n 의 모든 소인수에 대한 곱.

 

이제, 위 공식을 활용하여 효율적으로 ϕ(n)을 구하는 방법을 살펴보자.

1. 초기값을 설정: ϕ(n)=n
2. 2부터 sqrt(n)​ 까지의 소인수를 찾음:
   • 만약 p 가 n 의 약수이면, n을 p 로 나누면서 제거.
   • 동시에 ϕ(n) 값을 ϕ(n) -= ϕ(n)​/p 으로 업데이트.
3. 마지막으로 남은 소수가 있다면 한 번 더 처리.

 

시간 복잡도 분석

• 소인수분해는 sqrt(n)에 수행 가능.
• 따라서 전체 알고리즘의 시간 복잡도는 O(sqrt(n​)).
• 이는 n 이 매우 클 때도 빠르게 동작할 수 있도록 보장한다.

// Baekjoon Online Judge Problem. 11689

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	long long n;
	cin >> n;

	long long answer = n;

	for (long long i = 2; i <= sqrt(n); i++) {

		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			answer -= answer / i;
		}
	}

	if (n > 1)
		answer -= answer / n;

	cout << answer;

	return 0;
}