BOJ #1978 소수 찾기

문제

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

입력

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

출력

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

 

---

소스코드(C언어)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N;
	int test[110] = { 0 };
	int iscmp[1100] = { 0 }; //0이면 소수, 1이면 복소수
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &test[i]);

	iscmp[0] = iscmp[1] = 1;
	for (int i = 2; i <= 1000; i++)
		if (iscmp[i] == 0)
			for (int j = i + i; j <= 1000; j += i)
				iscmp[j] = 1;

	int num = 0;
	for (int i = 0; i < N; i++) {
		if (iscmp[test[i]] == 0)
			num++;
	}

	printf("%d\n", num);
}

 

Idea

에라토스테네스의 체를 이용한다.