Chap 7 정수론

1. 소수 구하기

1) 에라토스테네스의 체

에라토스테네스의 체의 원리
1. 주어진 범위까지의 배열 생성(1은 제외하고 2부터)
2. 선택한 수의 배수를 모두 삭제(ex, 2의 배수를 모두 삭제)
3. 다음 지워지지 않은 수(3)을 선택, -> 3의 배수를 모두 삭제, 이때 이미 지운 수는 다시 지우지 않음
4. 앞의 과정을 배열의 끝까지 반복
5. 삭제되지 않은 수를 모두 출력

에라토스테네스 체의 시간복잡도 -> 문제마다 다름 O(N^2) or O(Nlog(logN))

2) 문제1: 소수구하기 1929

1. 문제: https://www.acmicpc.net/problem/1929
   

2. 코드

• 2가 소수 -> 2의 배수들 모두 isPrime: false 처리

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

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

	int m, n;
	cin >> m >> n;

	vector <bool> isPrime(n + 1, true);
	isPrime[0] = false;
	isPrime[1] = false;

	for (int i = 2; i * i <= n; i++) { 
		if (isPrime[i]) {
			for (int j = i * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}  
	}

	for (int i = m; i <= n; i++) {
		if (isPrime[i]) cout << i << "\n";
	}
	return 0;
}

3) 문제2: 거의 소수 1456

1. 문제
   https://www.acmicpc.net/problem/1456
   소수의 제곱의 개수를 찾는 문제

2. 코드

• 범위 -> int 가 아닌 longlong을 써야함!
• 거의 소수 구할 때 a와 b사이 범위 안에서 카운트 하도록 조건 넣어줘야함!

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ll a, b;
	cin >> a >> b;
	int limit = sqrt(b) + 1;
	vector <bool> isPrime(limit + 1, true);
	vector <int>primes;
    
	//소수구하기
	for (ll i = 2; i <= limit; i++) {
		if (isPrime[i]) {
			primes.push_back(i);
			for (ll j = i * i; i <= b; j += i) {
				isPrime[j] = false;
			}
		}
	}
	
	//거의 소수 구하기
	ll cnt = 0;
	for (ll i : primes) {
		ll temp = i * i;
		while (temp <= b) {
			if (temp >= a) {
				cnt++;
			}
			if (temp > (b / i)) break;
			temp *= i;
		}
	}
	cout << cnt;

	return 0;
}

3) 문제3: 소수&팰린드롬 1747번

1. 문제 https://www.acmicpc.net/problem/1747
   

2. 코드

• 팰린드롬 <- 투포인터로 찾기
  숫자를 문자열로 바꾼 후, 투포인터를 이용해 비교

#include<iostream>
#include<vector>
#include<string> 
using namespace std; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력받기
	int n;
	cin >> n;

	vector <bool> isPrime(10000001, true);
	isPrime[0] = false; isPrime[1] = false;

	string num;
	bool pen = false;
    
	//소수를 찾기
	for (int i = 2; i*i<= 10000000; i++) {
		if (isPrime[i]) {
			for (int j = i * i; j <= 10000000; j += i) {
				isPrime[j] = false;
			}
		}
	}

	//소수의 값을 char 형태로 변환 후 투포인터를 이용해 팰린드롬 여부 확인
	for (int i = n; i <= 10000000; i++) {
		if (isPrime[i]) {
			pen = true;
			num = to_string(i);
			int ind1 = 0; int ind2 = num.length()- 1;
			while (ind1 <= ind2) {
				if (num[ind1] == num[ind2]) {
					ind1++;
					ind2--;
				}
				else {
					pen = false;
					break;
				}
			}
		}
		if (pen) {
			cout << num;
			break;
		}
	}
	return 0;

}

1016번

오일러피 관련 문제: 11689
유클리드 호제법 문제: 1934 1850 1033
확장 유클리드 호제법: 21568