728x90
시간 제한 : 2초
메모리 제한 : 128MB
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
소스코드
#include <iostream> #include <math.h> using namespace std; int sosu(int n) { int i, cnt = 0; if (n == 1) { return 0; } else if (n == 2 || n == 3) { return 1; } else if (n % 6 == 1 || n % 6 == 5) { for (i = 1; i <= sqrt(n); i++) { if (n%i == 0) { cnt++; } if (cnt > 1) { return 0; } } return 1; } else { return 0; } } int main(void) { int n; int arr[100]; int cnt = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } for (int i = 0; i < n; i++) { if (sosu(arr[i]) == 1) { cnt++; } } cout << cnt; }
Tip
에라토스테네스의 체를 이용하는 것도 괜찮지만, 제한 사항이 그렇게 타이트하지 않기 때문에 간단한 소수 판단 방식에 조금의 요령(6k+1, 6k+5를 제곱근까지만 확인하는)을 더하면 쉽게 풀 수 있다.
728x90
'Computer Science > Algorithm Problem' 카테고리의 다른 글
백준] 1193 - 분수찾기 (0) | 2018.04.10 |
---|---|
백준] 1712 - 손익분기점 (0) | 2018.04.09 |
백준] 3046 - R2(COCI 2006/2007) (0) | 2018.03.29 |
백준] 1316 - 그룹 단어 체커 (0) | 2018.03.29 |
백준] 1057 - 토너먼트 (0) | 2018.03.12 |