(백준BAEKJOOB )- 2960번- 에라토스테네스의 체 "c++"

일단 문제를 풀기 위해선 에라토스테네스의 체라는 알고리즘 (대량의 소수를 찾을 때 사용)을 

알고 있어야 시도가 가능하였다.

먼저 소수 구하기 https://www.acmicpc.net/problem/1929 문제와 비슷하여 참고하였다. 

 

 

#include <iostream>
#define MAX 1001
using namespace std;

int number=10;  //number를 10이라고 치면
int a[MAX];
void pa() {
	for (int i = 2; i <= number; i++) { //2부터 10까지 인덱스에 숫자를 저장해줌 1 2 ..10;
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) { //그리고 2부터 10까지 중에
		if (a[i] == 0) continue; //만약 지워진 숫자라면 그냥 내버려 두고 지나감
		for (int j = i + i; j <= number; j = j + i) { //2라는 숫자는 내버려두고 4부터 2의배수를 전부다 0으로만들어줌
			a[j] = 0;
		}

	}

	for (int i = 2; i <= number; i++) { //숫자 2부터 10까지 중에서 0이아닌 수를 출력
		if (a[i] != 0) printf("%d", a[i]);
	}


}

int main(void) {
	pa();
}

이건 간단한 수를 number에 대입하면

소수를 찾아주는 프로그램이다. 자세한 건 주석에 적어놨다.

이걸 기반으로 이 문제를 풀어봐야겠다.

 

 

문제를 잘 읽어보니 일단 

10으로 기준잡으면

1. 2부터 10까지 모든 정수를 적는다 = 2 3 4 5 6 7 8 9 10

 

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 p라고 하고, 이 수는 소수이다

그것은 2이다.

 

3.p를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지운다.

2의 배수는 2 4 6 8 10

 

4. 아직 모든 수를 지우는 수를 구하는 프로그램을 작성하시오.

다음수는 3이니까 3 9

6은 이미 지워졌으니까

다음 수 5 7 결국

순서는 2, 4, 6, 8, 10, 3, 9, 5, 7 대로 지워짐

k는 7 결국 7번째 지워진 숫자는 9니까 

출력값은 9가 나오는 것이다.

 

이것을 토대로 코드를 짜보겠다.

 

2부터 n까지의 숫자를

10까지로 가정하고 하겠습니다

	for (int i = 2; i <= number; i++) { 
		a[i] = i;
	}

 

2~10까지 인덱스에 저장

 

 

for (int i = 2; i <= number; i++) { 
		if (a[i] == 0) continue; 
		for (int j = i; j <= number; j = j + i) {
			if (a[j] != 0) {
				a[j] = 0;
				cnt++;
			}

 

2부터 10까지 범위를 정하고 

만약 a [i]=0이라면 넘어가고 

두 번째 for문에서는 j가 2의 배수 3의 배수 ~... 계속 지워나간다.

 

여기서 내가 잘못 생각하고 있던 게 있다.

for문은 (초기화 조건 증감식)

이렇게 돌아간다.

나는 조건식만큼 반복된다고 생각하고 있었지만 

잘 생각해 보면 for(int j=2 j <=10 j=4)

라는 뜻은 j가 4가 될 때까지 반복하겠다는 뜻이더라고요 

너무 기초기 때문에 아무 생각 없이 풀었네요..

 

 

 

 

			if (cnt == n) {
				res = j;
				break;
			}
			if (res != 0) break;
		}

그리고 cnt가 n가 같아지면 7번째 수를 res에 저장을 합니다

첫번째 for문도 탈출해주고 

 

	cout << res;

res출력하면 원하는 값이 나온다.

 

총 코드

---

 

#include <iostream>
#define MAX 1001
using namespace std;

int a[MAX];
int main(void) {
	int number,n;  
	int cnt = 0;
	int res = 0;

	cin >> number>>n;

	for (int i = 2; i <= number; i++) { 
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) { 
		if (a[i] == 0) continue; 
		for (int j = i; j <= number; j = j + i) {
			if (a[j] != 0) {
				a[j] = 0;
				cnt++;
			}
			

			if (cnt == n) {
				res = j;
				break;
			}
			if (res != 0) break;
		}

	}
	cout << res;


}