-
구간 체법
-
인접 소수 간 거리 https://www.acwing.com/problem/content/198/두 정수 L과 U가 주어졌을 때, 닫힌 구간 [L,U] 내에서 가장 가까운 인접 소수 쌍 C1과 C2(즉, C2-C1이 가장 작은 쌍)를 찾아야 합니다. 만약 동일한 거리를 가진 다른 인접 소수 쌍이 존재한다면, 첫 번째 쌍을 출력합니다.동시에, 가장 먼 거리를 가진 인접 소수 쌍 D1과 D2(즉, D1-D2가 가장 큰 쌍)도 찾아야 합니다. 동일한 거리를 가진 다른 쌍이 존재할 경우 첫 번째 쌍을 출력합니다.
입력 형식
각 줄에는 두 정수 L과 U가 입력되며, L과 U의 차이는 1,000,000을 초과하지 않습니다.
출력 형식
각 L과 U에 대해 결과를 한 줄에 출력합니다.
결과에는 가장 가까운 인접 소수 쌍과 가장 먼 인접 소수 쌍이 포함됩니다. (구체적인 형식은 예시 참조)
만약 L과 U 사이에 인접 소수 쌍이 존재하지 않는다면, "There are no adjacent primes."를 출력합니다.
데이터 범위
1≤L<U≤231−1
입력 예시:
2 17
14 17
출력 예시:
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.<br></br><br></br>소수 쌍 간의 거리를 판단하는 방법<br></br>먼저 해당 구간에 속한 소수를 찾아야 합니다. 데이터 범위가 매우 넓기 때문에, n의 제곱근까지만 판단한 후 확장하여 구간 내의 배수를 체로 걸러내는 방식을 사용합니다. L=1인 특수한 경우에 주의해야 합니다.<br></br>구체적인 내용은 코드를 참조하시기 바랍니다.
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_LIMIT = 1e6 + 10;
int primeCount;
bool isComposite[MAX_LIMIT];
int primeList[MAX_LIMIT];
bool segmentSieve[MAX_LIMIT];
int result[MAX_LIMIT];
int leftBound, rightBound;
void generatePrimes(int upperLimit) {
for(int i = 2; i <= upperLimit; i++) {
if(!isComposite[i]) {
primeList[++primeCount] = i;
}
for(int j = 1; j <= primeCount && i * primeList[j] <= upperLimit; j++) {
isComposite[i * primeList[j]] = true;
if(i % primeList[j] == 0) break;
}
}
}
int main() {
generatePrimes(50000); // sqrt(2^31)의 정수 부분, 왜냐하면 n의 약수 d는 sqrt(n)보다 작거나 같기 때문
while(cin >> leftBound >> rightBound) {
fill(segmentSieve, segmentSieve + MAX_LIMIT, false);
if(leftBound == 1) segmentSieve[0] = true;
for(int i = 1; i <= primeCount; i++) {
long long start = max((long long)ceil(leftBound / (double)primeList[i]), (long long)1);
long long end = floor(rightBound / primeList[i]);
for(long long j = start; j <= end; j++)
if(j != 1)
segmentSieve[j * primeList[i] - leftBound] = true; // 배열 이동
}
// 소수 표시
int primeNum = 0;
for(int i = 0; i <= rightBound - leftBound; i++) {
if(!segmentSieve[i])
result[++primeNum] = i + leftBound;
}
int maxDistance = 0, minDistance = INT_MAX;
int closestFirst, closestSecond, farthestFirst, farthestSecond;
// 인접 소수 쌍을 비교하여 최대/최소 거리 찾기
for(int i = 1; i < primeNum; i++) {
int currentDiff = result[i + 1] - result[i];
if(currentDiff > maxDistance) {
maxDistance = currentDiff;
farthestFirst = result[i];
farthestSecond = result[i + 1];
}
if(currentDiff < minDistance) {
minDistance = currentDiff;
closestFirst = result[i];
closestSecond = result[i + 1];
}
}
if(maxDistance == 0 || minDistance == INT_MAX)
cout << "There are no adjacent primes." << endl;
else
cout << closestFirst << "," << closestSecond << " are closest, "
<< farthestFirst << "," << farthestSecond << " are most distant." << endl;
}
return 0;
}
코드 보기197. 계승 분해 https://www.acwing.com/problem/content/199/
정수 N이 주어졌을 때, N!을 소인수분해하고, 산술 기본 정리의 형식으로 분해 결과에서 pi와 ci를 출력합니다.
입력 형식
하나의 정수 N.
출력 형식
N!을 소인수분해한 결과를 여러 줄에 출력합니다. 각 줄은 pi, ci 한 쌍으로, pi의 ci 제곱항이 포함됨을 의미합니다. pi의 오름차순으로 출력합니다.
데이터 범위
1≤N≤106
입력 예시:
5
출력 예시:
2 3
3 1
5 1
예시 설명
5!=120=23∗3∗5
접근법 1: 먼저 n의 소인수를 찾은 후, 1부터 n까지의 각 수를 판단하는 방법. 시간 복잡도 O(n * √n)로 시간 초과 발생
접근법 2: 접근법 1을 개선하여, 각 소인수 p에 대해 n 내에 p, p², p³,...가 몇 개인지 배수법으로 계산. 시간 복잡도는 O(nlogn) (logn의 합이며, 총 n개의 수)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 const int MAX_N = 1e6 + 10;
6 int n, primeCount;
7 bool isNotPrime[MAX_N];
8 vector<int> primes;
9
10 void sieve() {
11 for(int i = 2; i <= n; i++) {
12 if(!isNotPrime[i]) {
13 isNotPrime[i] = true;
14 primes.push_back(i);
15 }
16 for(int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
17 isNotPrime[i * primes[j]] = true;
18 if(i % primes[j] == 0) break;
19 }
20 }
21 }
22
23 int main() {
24 ios::sync_with_stdio(false);
25 cin.tie(nullptr);
26 cin >> n;
27 sieve();
28
29 for(int prime : primes) {
30 int count = 0;
31 int temp = n;
32 while(temp) {
33 count += temp / prime;
34 temp /= prime;
35 }
36 cout << prime << " " << count << endl;
37 }
38 return 0;
39 }
코드 보기```