문 제

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

입 력

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

4
1 3 5 7

출 력

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

3

코 드

using System;
using static System.Console;
using System.Linq;

namespace Algorithm
{
class Program
{
static void Main(string[] args)
{
int numCount = int.Parse(ReadLine());
int[] array = ReadLine().Split(' ').Select(int.Parse).ToArray();
int result = CountPrimes(array);

            WriteLine(result);
        }

        // === 에라토스테네스의 체 === //
        static int CountPrimes(int[] array)
        {
            int maxNum = array.Max();
            bool[] isPrime = new bool[maxNum + 1];
            int primeCount = 0;

            for (int i = 2; i <= maxNum; i++)
                isPrime[i] = true;

            for (int i = 2; i <= maxNum; i++)
            {
                if (isPrime[i] == false)
                    continue;

                for (int j = i + i; j <= maxNum; j += i)
                    isPrime[j] = false;
            }

            foreach (int num in array)
            {
                if (num >= 2 && isPrime[num])
                    primeCount++;
            }

            return primeCount;
        }
    }

}

비교코드 - 1

공 부

에라토스테네스의 체

void CalcPrime(int num)
{
    int[] temp = new int[num + 1];

    for(int i = 2; i < num; i++)
    	temp[i] = i;

    for(int i = 2; i <= num; i++)
    {
    	if (temp[i] == 0)
            continue;

    	for(int j = i + i; j <= num; j += i)
    	{
    		temp[j] = 0;
    	}
    }

}

1. 2부터~num까지 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다. (반복)

장점 : 대량의 숫자들 사이에서 소수 숫자 구하기에 적격!

약수 분해에 비해 소모시간 절반 소모! ```