[BOJ-1978][C++] 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

예제 입력 1

4
1 3 5 7

 

예제 출력 1 

3

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

문제 출처

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

1978번: 소수 찾기

 

문제 해결 방법

• 소수 찾기 알고리즘을 사용하여 간단하게 문제를 해결하였다.
  • 소수(Prime Number)란, 약수가 1과 자기 자신인 수를 의미한다.
  • 1부터 자기 자신의 수가 나올 때까지 for 문을 돌리면서, 나누어 떨어질 경우 약수의 개수를 1개씩 늘린 후, for 문을 빠져나올 때 약수의 개수가 2개일 경우 소수의 총개수(cnt)를 1씩 증가시킨다.
  • 이 과정을 N번 반복한다.

 

코드

#include <iostream>
using namespace std;

int N, num, prime, cnt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

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

        prime = 0;
        for (int i = 1; i <= num; i++) {
            if (num % i == 0) {
                prime++;
            }
        }
        if (prime == 2) {
            cnt++;
        }
    }

    cout << cnt << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기본 수학 2]
• 실버V