[Baekjoon] Class2 11 - 소수 찾기 [1978]

소수 찾기 [1978번]

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

입력

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

출력

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

생각해볼점

소수 구하기[[1929]]와 거의 동일한 문제다.

코드 구현

#include <stdio.h>

static int	is_prime(int num)
{
	int	i = 3;

	if ((num != 2 && num % 2 == 0) || num == 1)
		return (0);
	while (i * i <= num)
	{
		if (num % i == 0)
			return (0);
		i += 2;
	}

	return (1);
}

int main()
{
	int	num, idx, what_num, temp, arr[1001], count = 0;

	scanf("%d", &num);
	
	idx = -1;
	while(++idx <= 1000)
		arr[idx] = idx;

	idx = 2;
	while(idx * idx <= 1000)
	{
		if (is_prime(idx) == 1)
		{
			temp = 2;
			while(idx * temp <= 1000)
			{
				arr[idx * temp] = 0;
				temp++;
			}
		}
		if (idx == 2)
			idx++;
		else
			idx += 2;
	}

	while (num-- > 0)
	{
		scanf("%d", &what_num);
		if (arr[what_num] > 1)
			count++;
	}

	printf("%d", count);
	return (0);
}