1978 - 소수 찾기

• 난이도: 실버 5
• 날짜: 2023년 2월 3일
• 상태: Correct
• 추가 검토 여부: Yes

solution

• N개의 수를 2부터 $\sqrt{N}$까지 1씩 증가시켜가며 나누어 항상 나머지가 존재한다면 소수, 그렇지 않다면 합성수로 분류한다.
• 1은 소수도 합성수도 아니므로 예외처리한다.
• 굉장히 간단한 문제이고, 위의 알고리즘으로도 제한시간 내에 문제없이 해결 가능하지만 위의 알고리즘보다 세련된 알고리즘을 찾을 수 있을 것 같다.

code

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int * input = new int[N];
    for(int i = 0; i < N; i++)
        scanf("%d", &input[i]);
    int count = 0;
    bool prime;

    for(int i = 0; i < N; i++)
    {
        prime = true;
        if(input[i] == 1)
            prime = false;
        for(int j = 2; j <= sqrt(input[i]); j++)
        {
            if(input[i] % j == 0)
            {
                prime = false;
                break;
            }
        }
        if(prime) count++;
    }

    cout << count << endl;
    return 0;
}

ref

1978번: 소수 찾기