Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피)

 

Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피)

 

 

소수 구하기(에라토스테네스의 체 원리)

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

● 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 숫자의 배수들을 배열에서 모두 지우기

● 처음으로 선택된 숫자들은 지우지 않고 반복문을 N의 제곱근까지만 돌림

● 시간 복잡도는 O(Nlog(logN))

 

 

백준 1929번 소수 구하기

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

1929번: 소수 구하기

 

※ N의 범위가 1,000,000까지이므로 에라토스테네스의 체의 원리로 풀기 ※

● 배열의 마지막 인덱스부터 반복문을 돌리면서 A[i]가 K보다 작은 부분 찾아주기

● count에는 K를 A[i]로 나눈 몫을 더해주고 K는 K를 A[i]로 나눴을 때 나머지 값으로 갱신

 

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

int A[1000001];

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

	int M, N;
	cin >> M >> N;
	
	for (int j = 2; j <= 1000000; j ++)
		A[j] = j;

	for (int i = 2; i <= sqrt(1000000); i++) {
		if (A[i] == 0)
			continue;
		for (int j = i + i; j <= 1000000; j += i)
			A[j] = 0;
	}

	for (int i = M; i <= N; i++) {
		if (A[i] != 0)
			cout << i << '\n';
	}
}

 

 

 

백준 1456번 거의 소수

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

1456번: 거의 소수

 

 

※ 에라토스테네스의 체 이용해서 문제 풀기 ※

● 10의 7승까지 소수를 에라토스테네스의 체를 이용해서 모두 구하기

● 1,000,000까지 반복문을 돌리면서 만약 A[i]가 소수라면 MIN과 MAX사이에 있는 제곱수 모두 더해주기

● N^k < B형태인데 변수 범위를 초과하므로 N < B / N^k-1형태로 변환해서 계산하기

 

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

int A[1000001];

int main() {

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

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

	for (int j = 2; j <= 1000000; j++)
		A[j] = j;

	for (int i = 2; i <= sqrt(1000000); i++) {
		if (A[i] == 0)
			continue;
		for (int j = i + i; j <= 1000000; j += i)
			A[j] = 0;
	}

	int count = 0;
	for (int i = 2; i <= 1000000; i++) {
		if (A[i] != 0) {
			long temp = A[i];
			while ((double)A[i] <= (double)N / (double)temp){
				if ((double)A[i] >= (double)M / (double)temp)
					count++;
				temp *= A[i];
			}
		}
	}
	cout << count;
}

 

 

 

백준 1747번 소수&펠린드룸

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

1747번: 소수&팰린드롬

 

※ 에라토스테네스의 체 이용해서 문제 풀기 ※

● 1,000,000까지 소수를 에라토스테네스의 체를 이용해서 모두 구하기

● N~1,000,000까지 반복문 돌리면서 소수이면서 펠린드롬인 수 찾기

● 펠린드롬인지 확인하는 함수 만들어서 사용하기(숫자를 배열로 변환하고 투 포인터로 펠린드롬 확인)

 

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

int A[1000001];

bool isP(int n);
int main() {

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

	int K;
	cin >> K;

	for (int j = 2; j <= 1000000; j++)
		A[j] = j;

	for (int i = 2; i <= sqrt(1000000); i++) {
		if (A[i] == 0)
			continue;
		for (int j = i + i; j <= 1000000; j += i)
			A[j] = 0;
	}

	for (int i = K; i <= 1000000; i++) {
		if (A[i] != 0 && isP(i)) {
			cout << i;
			return 0;
		}
	}	
}

bool isP(int n) {
	string str = to_string(n);
	char const* temp = str.c_str();
	int start = 0;
	int end = str.size() - 1;

	while (start < end) {
		if (str[start] != str[end])
			return false;
		start++;
		end--;
	}
	return true;

}

 

 

 

백준 1016번 제곱 ㄴㄴ수

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

1016번: 제곱 ㄴㄴ 수

 

※ 에라토스테네스의 체 형식을 이용해서 문제 풀기 ※

● 소수를 구하는 것이 아닌 에라토스테네스의 로직을 따와서 풀기

● 주어진 범위에 있는 수들을 제곱수로 나누면서 확인해주기

● 일반적인 for문으로 돌리면 시간초과가 발생하므로 제곱수의 배수 형태로 탐색하기

 

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

int main() {

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

	long MIN, MAX;
	cin >> MIN >> MAX;
	vector<bool>check(MAX- MIN + 1);

	for (int i = 2; i * i <= MAX; i++) {
		long pow = i * i;
		long start_index = MIN / pow;

		if (MIN % pow!= 0)
			start_index++;

		for (long j = start_index; j * pow <= MAX; j++) {
			check[(int)((j * pow) - MIN)] = true;
		}
	}
	int count = 0;
	for (int i = 0; i < check.size(); i++) {
		if (!check[i])
			count++;
	}
	cout << count;
}

 

 

 

오일러 피

● 1부터 N까지 범위에서 N과의 서로수의 개수를 나타냄 = P[N]

● 오일러 피 함수의 원리

   1. N까지의 배열을 만들고 A[i]=i로 각 배열을 초기화

   2. 반복문을 돌리면서 A[i]==i라면(소수) 현재 선택된 숫자(k)의 배수들을 모두 A[i] = A[i]-A[i]/k로 업데이트

   3. 모든 탐색을 마치고 각 배열에 남아있는 숫자들은 1부터 각 숫자들 범위 안에 있는 서로수의 개수

 

 

백준 11689 GCD(n,k)=1

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

11689번: GCD(n, k) = 1

 

※ 오일러 피 함수를 구현하는 문제 ※

● 2~N제곱근까지 반복문을 돌리면서 N의 소인수 찾기

● 만약 N의 소인수라면 result = result-result/p로 갱신하고 n을 p로 나눌 수 있을 만큼 나눠주기

● 반복문을 다 돌리고 나서 n이 1보다 크면 result를 n으로 소인수를 하지 못한 것임

● 그러므로 한 번 더 result = result-result/n으로 result값 업데이트

 

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

int main() {

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

	long n;
	cin >> n;

	int result = n;
	for (long p = 2; p <= sqrt(n); p++) {
		if (n % p == 0) {
			result = result - result / p;
			while (n % p == 0)
				n /= p;
		}
	}
	if (n > 1)
		result = result - result / n;
	cout << result;
}