[백준] 1978번 : 소수 찾기 (C++)

---

문제

---

풀이

int 변수 N, num, decimal(소수의 개수), count(0이라면 소수X, 아니라면 소수O)를 선언했다.

소수는 1과 자기자신으로 나누었을 때만 나머지가 0이 된다.

반대로, 소수가 아닌 경우에는 1과 자기 자신 사이의 수로 나누면 나머지가 0이 되는 것을 이용했다.

 

아래의 코드와 같이, 소수가 아니라면 count++를 하였다. for문을 빠져나왔을 때 count == 0이라면 소수이므로 소수의 개수를 의미하는 변수인 decimal을 증가시켰다.

 

예를 들어, num = 9, j = 3이라면, 9 % 3 = 0이다. 이는 소수가 아니므로 count를 증가시킨다.

for문을 빠져나오면 count == 0인지 확인하는 if문을 통해, 소수라면 변수 decimal을 증가시킨다.

 

for (int j = 2; j < num; j++) {			
	if (num % j == 0) {					
		count++;
	}
}
if (count == 0) {	// count == 0인 소수만 decimal++
	decimal++;
}
count = 0;	//  count = 0으로 다시 초기화하기

 

주의해야할 점은 1은 소수가 아니고, 2는 소수인 점이다.

 

위처럼 for문을 사용할 때 2부터 num - 1까지의 숫자로 나누었다.

이 때문에, 1과 2는 for문을 통해 소수 여부가 구해지지 않아 if문을 이용하여 1은 소수가 아니니 count++를 하고, 2는 소수이므로 바로 decimal++을 해주었다.

 

for (int i = 0; i < N; i++) {
	cin >> num;

	if (num == 2) {	// 2는 소수
		decimal++;
	}
	else {
		if (num == 1) {	// 1은 소수가 아님!
			count++;
		}
		for (int j = 2; j < num; j++) {	// 소수X: num을 '2부터 num-1'으로 나눈 나머지가 0이라면 count++
			if (num % j == 0) {	// ex) num = 9, j = 3, 9 % 3 = 0 / 소수가 아니므로 count++
				count++;
			}
		}
		if (count == 0) {		// count == 0인 소수만 decimal++
			decimal++;
		}
		count = 0;				//  count = 0으로 다시 초기화하기
	}
}

 

---

코드

#include <iostream>
using namespace std;

int main() {
	int N, num, decimal=0, count=0;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;

		if (num == 2) {		// 2는 소수
			decimal++;
		}
		else {
			if (num == 1) {		// 1은 소수가 아님!
				count++;
			}
			for (int j = 2; j < num; j++) {			
				if (num % j == 0) {					
					count++;
				}
			}
			if (count == 0) {	// count == 0인 소수만 decimal++
				decimal++;
			}
			count = 0;			//  count = 0으로 다시 초기화하기
		}
	}

	cout << decimal;			// decimal 출력

	return 0;
}

---

결과