에라토스테네스의 체를 응용한 소수 사이 수열 3896

 
2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.

1. 2부터 시작해서 n까지 진행한다.
2. 가장 작은 수를 선택한다.
3. 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.

 

//에라토스테네스의 체로 1000까지의 소수 출력하기

#include<stdio.h>
#include<cmath>
using namespace std;


int main(){
	int n = 1000;
	int check[1001] = { false };

	check[0] = check[1] = true;
	for (int i = 2; i < sqrt(1000); i++){
		if (check[i] == false){
			for (int j = i + i; j <= 1000; j += i){
				check[j] = true;
			}
		}
	}

	for (int i = 1; i <= n; i++){
		if (!check[i]) printf("%d ", i);
	}
	


	return 0;
}

 
 
에라토스테네스의 시간 복잡도는 O(n*log(log(n))) 를 가진다.
 
 
제출한 답안

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<bool> sieve(1299710);
int prime[100000];



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

	int idx = 0;
	sieve[0] = 1;
	for (int i = 2; i < 1140; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1299710; j += i) sieve[j] = 1;
	}

	for (int i = 2; i < 1299710; i++) {
		if (sieve[i]) continue;
		prime[idx++] = i;
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		if (!sieve[x]) cout << 0 << '\n';
		else {
			int l, r;

			int L = 0, R = 99999;
			while (L < R) {
				int mid = (L + R) / 2;
				if (x < prime[mid]) R = mid;
				else L = mid + 1;
			}
			r = R;

			L = 0, R = 99999;
			while (L < R) {
				int mid = (L + R) / 2 + 1;
				if (prime[mid] < x) L = mid;
				else R = mid - 1;
			}
			l = L;

			cout << prime[r] - prime[l] << '\n';
		}
	}
}

 
 
나중에 둘 보면서 다시 코드 짜봐야겠다