https://www.acmicpc.net/problem/1929
문제
> M이상 N이하의 소수를 모두 출력해라.접근
소수 관련 문제는 에라토스테네스의 체를 이용한다.
에라토스테네스 체를 이용해서 소수를 구하고 범위가 주어지면 해당 범위 내의 소수를 출력한다.
문제해결
> M과 N의 범위가 1 <= N,M <= 1,000,000이므로 소수여부를 마킹해줄 bool벡터의 크기를 1,000,001로준다.(0번인덱스는 안쓰기 때문에 +1)
> 체를 구현한다. 1은 소수가 아니므로 1은 false해주고 2부터 탐색한다. 조건문 안에서 들어온 i의 배수들을 전부 false해준다. 배수라는건 약수가 존재한다는 뜻이므로 전부 제외해주는것이다.
> 먼저 i의 제곱, 자신의 제곱부터 false해주고 +i 즉, i의 배수를 최대 범위까지 증가시키며 전부 false해준다.
> 제곱부터 해주는 이유는 예를 들어 3이면 앞에서 2x3에서 이미 3x2가 나왔으므로 3x3부터 해주고, 4면 4x2는 2의 배수, 4x3은 3의 배수로 나왔기 때문이다. 즉 제곱수 이전 수는 전부 앞에서 배수로 나온다.
> 마킹이 끝났으면 main함수에서 주어진 범위 내 true인 수만 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int MAX = 1000001;
vector<bool> is_prime(MAX, true);
void sieve()
{
is_prime[1] = false;
for (long long i = 2; i < MAX; i++)
{
if (is_prime[i] == true)
{
for (long long j = i * i; j < MAX; j += i) is_prime[j] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int M, N;
cin >> M >> N;
sieve();
for (int i = M; i <= N; i++)
{
if (is_prime[i]) cout << i << '\n';
}
}
후기
브론즈에서 에라토스테네스의 체를 구현해본적이 있어서 기억을 더듬으며 했다. 체 구현하는 알고리즘을 다시 머릿속에 기억해두자.
