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

1978번: 소수 찾기

 

📚 문제 한 줄 요약

최대 100개의 1000보다 작은 수가 주어졌을 때 소수가 몇 개인지 구하기

 

📚 풀이 (핵심 : 어떻게 소수인지 판별하는 연산을 구현할 것인가?)

문제 해결 순서는 다음과 같이 계획했다.

1. 입력 데이터 받기 (숫자의 개수 N, 숫자)
2. 소수 구하기
3. 소수의 개수 출력하기

 

소수를 구하는 과정은 다음과 같이 구현했다.

		// 미리 소수 개수를 증가시킨다.(1은 소수가 아니므로 제외.)
		if (num >= 2)
			primeNum++;
            
		for (int i = 2; i*i <= num; i++) {// 소수인지 탐색한다.
			if (num%i == 0) { // 만약 소수가 아니라면 소수 개수를 감소시켜 값에 변화가 없게 한다.
				primeNum--; 
				break;
			}
		}

이때 탐색을 i*i* <= num까지 하는 이유는

그 이상의 값은 나눌 필요가 없기 때문이다.

 

약수는 가장 작은 값과 가장 큰 값 그리고 그다음으로 크고 작은 값이 서로 쌍을 이룬다.

예를 들어 36을 생각해보자. 36의 약수는 다음과 같다.

(2, 18), (3, 12), (4, 9), 6

보시다시피 2로 나누면 몫이 18이 나오는데 18로 나누면 몫이 2가 나올 것이다.

제곱근인 6은 자신을 두번 곱하는데 6 이상의 값인 9, 12, 18은 2, 3, 4에서 몫과 나누는 값만 바뀌는 것이기 때문에 고려할 필요가 없는 것이다.

 

---

📚 전체 Code