[BOJ/1929/C++] 소수 구하기

 

소수 구하는 문제라 쉬울 거라고 생각하고 자신있게 문제를 풀었다..

그래서 아래와 같이 구했고, 답도 제대로 나왔다.

#include<iostream>
#include<vector>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int M, N;
	vector<int> vector;
	cin >> M >> N;
	for (int i = M; i <= N; i++) {
		int count = 0;
		for (int j = 2; j < i; j++) {
			if (i % j != 0) {
				count++;
				if (count == i - 2) {
					vector.push_back(i);
					break;
				}
			}
			else break;
		}
	}
	for (auto& i : vector) {
		cout << i << endl;
	}
	return 0;
}

 

그러나 오늘도 어김없이 나오는 시간초과,,

 

그래서 찾아보니 에라토스테네스의 체 라는 방법이 있었다.

이게 뭐냐하면 2 이상의 구하고자 하는 범위 내에 존재하는 자연수를 모두 나열한 뒤, 2 이상 배수들을 차례로 지워나가는 방법이라고 한다!

 

에라토스테네스의 체의 시간복잡도는 O(N log(log N))으로 매우 빠르다.

    for (int i = 2; i * i <= N; i++) {
        if (vector[i] == 0) continue;
        for (int j = 2 * i; j <= N; j += i) {
            if (vector[j] == 0)  continue;
            else vector[j] = 0;
        }
    }

 

그래서 이를 활용했는데도 어김없이 등장한 시간초과,,

아래 사진은 내 노력의 결과물이다

 

최후로 사용해준 방법은 cin, cout이 아닌, <cstdio> 헤더를 사용해서 scanf() prinf()로 바꿔준 것이다.

 

최종 코드는 아래와 같다.

#include <cstdio>
#include <vector>
using namespace std;
int main(void) {
    int M, N;
    scanf("%d %d", &M, &N);

    vector<int> vector(N + 1, 0);

    for (int i = 2; i <= N; i++) {
        vector[i] = i;
    }

    for (int i = 2; i * i <= N; i++) {
        if (vector[i] == 0) continue;
        for (int j = 2 * i; j <= N; j += i) {
            if (vector[j] == 0)  continue;
            else vector[j] = 0;
        }
    }

    for (int i = M; i <= N; i++) {
        if (vector[i] != 0) printf("%d\n", vector[i]);
    }
    return 0;
}