[4일차] 정수론 D - 2960: 에라토스테네스의 체

실버 Ⅳ

 

#include <iostream>
#include <vector>
using namespace std;

int N, K;
bool check[4000001];

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; i++) check[i] = true;

	int cnt = 0;

	for (int i = 2; i <= N; i++) {
		for (int j = i; j <= N; j += i) {
			if (!check[j]) continue;
			check[j] = false;
			cnt++;
			if (cnt == K) {
				printf("%d", j);
				return 0;
			}
		}
	}
}

그냥 배열을 체크하는 용도로만 쓴다면 위와 같이 할 수 있고

배열에 소수인지 아닌지 기록하려면

for문에서 첫번째는 빼줘야 하니까

밑에 코드처럼 해야함

#include <iostream>
#include <vector>
using namespace std;

int N, K;
bool isPrime[4000001];
vector<int> primes;

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; i++) isPrime[i] = true;

	int cnt = 0;
	
	for (int i = 2; i <= N; i++) {
		printf("i: %d\n\n", i);
		//소수가 아니면 넘기기
		if (!isPrime[i]) continue;
		//소수라면 배수 다 지워주기
		printf("%d 소수임\n", i);
		cnt++;
		if (cnt == K) {
			printf("%d", i);
			return 0;
		}
		for (int j = i + i; j <= N; j += i) {
			//이미 아니라고 체크됐으면 넘기기
			if(!isPrime[j]) continue;
			isPrime[j] = false;
			printf("%d 소수아님\n", j);
			cnt++;
			if (cnt == K) {
				printf("%d", j);
				return 0;
			}
		}
	}
}

연습할 때 돌려보라고 print도 넣어놨고...

암튼 그렇다

이거는 에라토스테네스에서 실제로 지우는 횟수를 세야하므로

루트 N 까지만 해볼 수가 없음 ㅇㅋㅇㅋ??

나는 그렇게 생각함 아닐 수도있고 근데 맞을걸