백준 1978번 (소수 찾기)

오늘은 백준 1978번 문제를 풀었다.
처음에는 단순히 홀수만 걸러서 소수라고 생각했는데, 9나 15처럼 홀수지만 소수가 아닌 수들이 있다는 걸 다시 한번 깨달았다.

결국 중요한 건 약수가 1과 자기 자신밖에 없는 수가 소수라는 점이다.
그래서 2부터 √n까지 나눠봤을 때 나머지가 0인 게 하나라도 있으면 소수가 아니다라는 기준으로 판별해야 했다.

C#에서는 지역 함수로 IsPrime()을 만들어서 소수 판별을 처리했다.
i * i <= num 조건으로 루프를 도는 게 효율적인 점도 알게 됐다.

int a = int.Parse(Console.ReadLine());

int[] input = new int[a];

input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

int output = 0;
for (int i = 0; i < input.Length; i++)
{
    if (IsPrime(input[i]))
        output++;
}


bool IsPrime(int num)
{
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

Console.WriteLine(output);

처음에는 소수의 정의도 헷갈렸지만, 직접 구현해보고 조건들을 하나씩 정리하면서 확실하게 이해할 수 있었다.