[BOJ][C++] 백준 1978번 소수 찾기
Updated:
1978 소수 찾기
1. 문제 정보
백준 온라인 저지 [1978번 소수 찾기] 문제의 링크입니다.
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
예제 입력1
4
1 3 5 7
예제 출력1
3
시간 / 메모리 제한
2초 / 128MB
2. 생각
-
단순하게 생각해서 소수는 1과 자기 자신을 제외한 수로 나눠지지 않으므로 i를 2부터 num보다 작을 때까지 증가시켜 num이 i로 나눠지는지 판단하려고 했습니다. flag를 두어 나눠지면 소수가 아닌 것으로 판단합니다.
-
n으로 판단할 숫자를 입력받고 n번 들어온 각 숫자가 i로 나눠지는지 판단하고 소수가 아니면 카운트 변수의 값을 증가시키지 않습니다.
-
그렇게 하면 소수를 판별하는데에 O(n)의 시간이 걸리고 이 것을 n번 반복할 것입니다. n은 100이하의 자연수이고, 각 숫자는 1000이하의 자연수이므로 100*1000 = 100,000입니다. 시간제한 2초에 충분합니다. (대략 1억 = 1초)
+ 에라토스테네스의 체 방법을 사용할 수 있습니다.
소수 관련 알고리즘은 두 가지 있습니다.
- 주어진 소수가 소수인지 아닌지 판별하는 방법 (1978번 문제)
- 주어진 n보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 (에라토스테네스의 체 방법)
3. 소스코드 (C++)
