1978번 소수 찾기

#문제링크 : https://www.acmicpc.net/problem/1978

cnt : 소수 갯수 / a : 입력된 숫자를 담을 배열 / isPrime : 소수인지 판별하는 변수

전략 : 1, 2 ,3에 대해선 예외처리를 해주고 나머지 숫자가 주어지면 해당 숫자의 제곱근까지의 숫자로 그 숫자를 나눠서 나머지가 0이 되는 경우가 한번이라도 생기면 isPrime = false 처리하고 다음 숫자로 또 같은 판별을 진행.

제곱근까지만 나누는 이유는 100에 대해서 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이 되는데, 각 약수는 가장 작은 약수 X 가장 큰 약수 = 100, 그 다음 작은 약수 X 그 다음 가장 큰 약수 = 100(1*100=100, 2*50=100 ... )이므로 앞서 1과 2로 나누어 판별할 경우 이미 100과 50으로 나누어 판별하는 경우와 중복되므로 주어진 수의 제곱근보다 1 큰수까지 계산하고 다음 판별로 넘어가야 시간복잡도를 줄일 수 있다. 복잡도는 O(NrootN)이다.

Code