[S4] 백준 2960번 에라토스테네스의 체 C++ 소수 판정, 에라토스테네스의 체

리뷰

 

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

솔브닷 마라톤에 떠서 풀어본 문제

 

전역 변수

• n, k : 주어지는 정수의 범위 n, k번째 지워진 수를 찾기 위한 변수 k
• v : 이미 지워진 수를 방문처리 하기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. n ,k를 입력 받고, 지워진 숫자의 개수를 체크하기 위한 정수형 변수 idx를 0으로 초기화 한다.
2. 2부터 n까지 for문을 한번 돌리고, i부터 n까지 for문을 한번 더 돌려준다. 이때 증가값은 i여야 한다.
3. 만약 j가 이미 방문했던 정수라면 continue 처리를 해준다.
4. 방문하지 않은 정수라면 j에 방문처리를 해주고, idx를 증가시킨다.
5. idx가 k에 도달했다면 j를 출력해주고 main 함수를 리턴 해준다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
using namespace std;

int n, k;
int v[1001];

int main() {
	cin >> n >> k;
	int idx = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			if (v[j]) continue;
			v[j] = 1;
			idx++;
			if (idx == k) {
				cout << j;
				return 0;
			}
		}
	}
}