[백준] 2960번 에라토스테네스의 체

반응형
반응형

문제

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

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

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

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

입력

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

출력

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

 

이 문제는 생각보다 오래 걸렸다. 1시간 좀더 넘게 걸린것 같은데... 이제 어떻게 코딩해야 조금씩 감잡기 시작한것 같다.

#include <bits/stdc++.h>
using namespace std;

int n,k;
vector<int> s;

vector<bool> o;

vector<int> rs;

bool primir(int num) {
  if (num == 1) return false;

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



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cin >> n >> k;
  
  for(int i = 2;i<=n;i++) {
    if (primir(i)) {
      s.push_back(i);
    }
  }
  o.push_back(false);
  o.push_back(false);

  for(int i =2;i<=n;i++) {
    o.push_back(true);
  }
  
  int start = 0;
  while(start < s.size()) {
  for(int i = 2;i<=n;i++) {
    if (i%s[start] == 0 && o[i]) {
      o[i] = false;
      rs.push_back(i);
    }
  }
  start++;
  }

  cout << rs[k-1];

}

다음은 변수에 대한 내용입니다.

s => 소수를 저장합니다.

o => 출력가능 여부를 저장합니다.

rs => 결과를 저장합니다.

이 문제는 구현문제라 이렇게 풀었습니다.ㅎㅎ

먼저 소수를 구하는 작업을 가졌습니다.

그러면 배열에 2 3 5 7 ... 이라는 숫자가 저장됩니다.

 

그리고 나서 한참동안 고민했습니다.

그리고 문제에 나온 예제를 작성했습니다.

예제 같은 경우 최대 소수가 7이므로 갯수로는 4개입니다.(2,3,5,7)

이에 대한 값을 2부터 7까지 반복문을 사용하지 않고 

하나하나 입력했습니다.

그리고 답을 하나씩 체크해가면서 값을 추가해주었습니다.

이때 한 번이라도 해결된 숫자는 2번다시 등장하지 않기 위해 bool을 이용해서 처리했습니다.

 

+ 추가 o.push_back(false)인 이유는 vector는 2부터 추가해도 자연스럽게 0부터 넣어지기 때문에 이를 방지하고자 false를 넣었습니다. 지금 생각하니 안해도 될것 같군요.ㅡㅡ;

#include <stdio.h>
int N, K;
bool isPrime[1005];
int main(void) {
	scanf("%d %d", &N, &K);
	for(int i = 2; i <= N; i++)
		isPrime[i] = true;
	int cnt = 0;
	int i;
	for (i = 2; ; i++) {
		if (!isPrime[i]) // i가 소수가 아니면
			continue;
		for (int val = i; val <= N; val += i) {
			if (!isPrime[val])
				continue;
			cnt++;
			isPrime[val] = false;
			if (cnt == K) {
				printf("%d", val);
				return 0;
			}
		}
	}
}

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 1012번 유기농 배추  (0) 2020.08.08
[백준] 6198번 옥상 정원 꾸미기  (0) 2020.08.01
[백준] 1743번 음식물 피하기  (0) 2020.07.15
[백준] 1764번 듣보잡  (0) 2020.07.10
[백준] 7785번 회사에 있는 사람  (0) 2020.07.09

댓글

Designed by JB FACTORY