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

제출 코드

#include <iostream>
using namespace std;

bool isPrime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    int n = 1;

    cin >> n;
    while (n) {
        int cnt = 0;
        for (int i = n + 1; i <= 2 * n; i++) {
            if(isPrime(i)) cnt++;
        }

        cout << cnt << '\n';
        cin >> n;
    }
    
    return 0;
}

음 풀었는데 시간이 너무 오래걸린다!!

풀이 방식

전 포스트들과 똑같이 소수 판별할 때 그 수의 제곱근까지만 판별하면 되는데

에라토스테네스의 체 방식으로 풀어야 할거 같다

왜냐하면 소수 판별에 필요한 범위가 주워지기 때문이다.

구현이 어려워서 의사코드를 찾아봤다.

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

음 영어 어렵지만 하나하나 구현해보자

#include <iostream>
using namespace std;

int main(void) {
	int n;
    cin >> n;
    
    bool A[n];
    
    for (int i = 0; i < n; i++) {
    	A[i] = true;
    }
    
    for (int i =2; i * i < n; i++) {
    	if (A[i]) {
        	// i2, i2+i, i2+2i, i2+3i ???????????
        	for (int j = i * i; j <= n; j += i) { //그녀석의 도움
            	 A[j] = false;
            }
        }
    }
	return 0;
}

내일은 정말 이 기술을 마스터 해보자.