[ BOJ/C# ] 1978 소수 찾기

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

1978번: 소수 찾기

소수판별은 꽤나 기본적이면서 중요한 알고리즘이라고 생각해 풀어보았다. 

에라토스테네스의 체가 생각났지만, 이처럼 1000까지의 수 내의 주어진 수만 판별해야 한다면 다른 방법이 좋을 수도 있겠다고 생각했다. 

다음과 같은 방식으로 한다면 시간복잡도는 O(n√n)이다. 각각의 수 O(√n)의 총 O(n√n). 

using System;

namespace B1978
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(sr.ReadLine());
            int[] array = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            bool isPrime;
            int count = 0;

            for(int i = 0; i < array.Length; i++)
            {
                //소수인가?
                isPrime = IsPrime(array[i]);
                if (isPrime) count++;
            }
            sw.WriteLine(count);
            sr.Close();
            sw.Flush();
            sw.Close();
        }

        //소수 판별
        static bool IsPrime(int n)
        {
            if (n == 1) return false;
            for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
            return true;
        }
    }
}