🙇‍♀️[Silver IV] 에라토스테네스의 체 - 2960

문제 링크

성능 요약

메모리: 2024 KB, 시간: 0 ms

분류

구현, 수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 12월 21일 16:36:27

문제 설명

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

🚀풀이

문제의 알고리즘 순서대로 로직을 세워주면 된다.

일단 숫자들을 넣을 배열을 만들어주고 그 배열에는 1로 초기화해준다.

1로 초기화한다는 것은 아직 지워지지 않은 숫자라는 뜻이다.

2부터 n까지 순회하면서 지우기 시작하는데 중첩 for문으로 배수들을 먼저 지워준다.

지워줄때마다 cnt를 늘려주고 k와 같은 때 그때의 값을 출력하고 리턴한다.

위의 로직을 그대로 구현한 코드가 아래와 같다.

int n, k, cnt = 0;
int primes[1001] = { 0, };

void solve()
{
	cin >> n >> k;

	for (int i = 2; i <= n; ++i)
	{
		primes[i] = 1; // 1로 되어있다는 것은 지워지지 않은 수라는 뜻
	}

	for (int i = 2; i <= n; ++i)
	{
		for (int j = i; j <= n; j += i) // 배수들 지워주는 작업
		{
			if (primes[j] != 0)
			{
				primes[j] = 0; // 숫자 지워주기
				cnt++;
				if (cnt == k)
				{
					cout << j << '\n';
					return;
				}
			}
		}
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k, cnt = 0;
int primes[1001] = { 0, };

void solve()
{
	cin >> n >> k;

	for (int i = 2; i <= n; ++i)
	{
		primes[i] = 1;
	}

	for (int i = 2; i <= n; ++i)
	{
		for (int j = i; j <= n; j += i)
		{
			if (primes[j] != 0)
			{
				primes[j] = 0;
				cnt++;
				if (cnt == k)
				{
					cout << j << '\n';
					return;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고