[BOJ] 1978번 소수 찾기

문제

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

입력

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

출력

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

예제

// 입력
4
1 3 5 7

// 출력
3

코드

• C++17

#include <iostream>

using namespace std;

bool primes[1001] = { true, true };
int N, ans;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	// 에라토스테네스의 체
	for (int i = 2; i <= 1000; i++)
	{
		if (primes[i] == false)
		{
			for (int j = i * i; j <= 1000; j += i)
				primes[j] = true;
		}
	}

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		if (primes[num] == false)
			++ans;
	}

	cout << ans;
}

• C#

using System;

namespace AlgorithmsByCsharp
{
    class Program
    {
        static bool[] primes = new bool[1001];
        static int N, ans;

        static void Main(string[] args)
        {
            primes[0] = primes[1] = true;
            for (int i = 2; i <= 1000; i++)
            {
                if (primes[i] == false)
                {
                    for (int j = i * i; j <= 1000; j += i)
                    {
                        primes[j] = true;
                    }
                }
            }

            N = int.Parse(Console.ReadLine());
            string[] inputs = Console.ReadLine().Split();
            for (int i = 0; i < N; i++)
            {
                int index = int.Parse(inputs[i]);
                if (primes[index] == false)
                {
                    ++ans;
                }
            }

            Console.Write(ans);
        }
    }
}

• Python

import sys;

is_primes = [True for i in range(1001)]
for i in range(2, 1001):
    if is_primes[i]:
        for j in range(i * i, 1001, i):
            is_primes[j] = False
is_primes[0] = is_primes[1] = False

Ans = 0
N = int(sys.stdin.readline())
inputs = sys.stdin.readline().split(' ')
for i in inputs:
    if is_primes[int(i)]:
        Ans += 1
sys.stdout.write(str(Ans))