백준문제풀이 9단계 약수,배수와 소수(4) 1978번 소수 찾기 (C#)

 

자연수 N개를 받고 그 중에 소수가 몇개있는지 출력하는 문제.

 

using System;
class BackJoon
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split();
        int count = 0;

        for (int i = 0; i < N; i++)
        {
            int A = int.Parse(input[i]);
            if (IsPrime(A))
                count++;
        }

        Console.WriteLine(count);
    }

    static bool IsPrime(int num)
    {
        if (num < 2)
            return false;
        if (num == 2)
            return true;
        if (num % 2 == 0)
            return false;
        for (int i = 3; i <= Math.Sqrt(num); i += 2)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

 

먼저 개수N을 받고

N개의 자연수들을 string배열에 넣어준다.

N번 for문을 돌며 자연수들을 하나씩 검사해준다.

 

검사를 해주는 함수인 IsPrime

2보다 작을때는 false

2일때는 true

2로 나눴을때 나머지가 0인것을 false로 해서 짝수는 미리 제거를 해준다.

다음은 i = 3부터 루트num 까지 도는데 제곱근을 범위로 두는 이유는

이 숫자가 약수가 있는지 없는지만 확인 하면 되는거라서 루트N이하만 보면 된다.

예를들어 숫자가 64라면 약수는 1 , 2 , 4  , 8 , 16 , 32 , 64 이고

이는 [1,64] [2,32] [4,16] [8,8]로 각각 대응이된다.

따라서 루트 64인 8이하만 검사해주면 되므로 시간복잡도를 줄일수있다.

 

IsPrime함수가 true라면 count를 증가시켜주고

최종적으로 count를 출력해주면 끝이다.