[백준] 1978 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

알고리즘 공부를 하다가 소수 찾는 방식이 필요한 문제를 만나 이를 공부하려고 백준 문제를 풀었다. 

 

처음에는 소수 판정을 (만약에 N이라는 수)일 때 소수임을 알기 위해서 2부터 n-1까지의 숫자로 나눠서 파악했다.

 

하지만 연산량이 너무 많았고 나중에 N 이 커졌을 때는 시간 초과가 나타날 수 있음을 알았다. 

 

연산량을 줄이기 위해 한 가지 수학적인 사실을 알았다.

 

소수는 2부터 √n까지의 정수로 나눠보면 알 수있다. 

이를 이용하여  연산량을 줄여 문제를 풀 수 있었다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int N;
	cin >> N;

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

		if (num == 1) {
			continue;
		}
		else {
			bool is_true = true;
			for (int j = 2; j <= sqrt(num); j++) {
				if (num%j == 0) {
					is_true = false;
					break;
				}
			}
			if (is_true) {
				cnt++;
			}
		}
	}

	cout << cnt;
}