2960 에라토스테네스의 체

기본 알고리즘을 통해 확인할 수 있듯, 이번 문제는 에라토스테네스의 체를 이용하여 풀 수 있는 문제이다.

한가지 유의할 점은 이번 문제에서는 2와 3과 같은 출발(?) 하는 소수 또한 포함되어 계산한다는 점!

간단한 문제이므로 소스코드만 첨부하여 오늘의 알고리즘 풀이는 마친다.

<소스코드>

#include <cstdio>

int N, K,cnt;
bool visit[1001],flag;

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j*i <= N; j++) {
			if (!visit[i*j]) cnt++;
			visit[i*j] = true;
			if (cnt == K) {
				printf("%d\n", i*j);
				flag = true;
				break;
			}
		}
		if (flag == true) break;
	}
}