1978번 소수 찾기(C)

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

1978번: 소수 찾기

문제

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

 

사전지식

이미 소수 구하기(실버2 난이도)를 푼 적이 있어서, 이것을 이용하여 소수 찾기(실버4 난이도) 문제를 해결할 수 있겠다고 생각했다. 내가 전에 풀었던 소수 구하기의 메커니즘(에라토스테네스의 체)을 다시 사용했다.

https://detective.tistory.com/14

1929번 소수 구하기(C)

해결과정

소수 구하기가 되었으면, 별 거 없다. 한 배열에서 소수들을 미리 찾아놓고, 입력값의 수들이 소수에 해당하는지 for문을 통해 확인만 하면 되었다. arr[num[i]]같은 배열[배열] 표현을 실제로 잘 쓰는지는 모르겠는데, 이 생각밖에 안나서 뭔가 이상해보이긴하나 이렇게 시도해보았다.

코드

#include <stdio.h>
int arr[1001] = { 1,1 };

int main() {
	int N, max = 0;
	int num[1001];
	int i, j;
	int cnt = 0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &num[i]);
		if (num[i]>max) max = num[i];
	}

	for (i = 2; i <= max; i++) {
		if (!arr[i]) {
			for (j = i + i; j <= max; j += i)
				arr[j] = 1;
		}
	}

	for (i = 0; i < N; i++) {
		if (arr[num[i]] == 0) cnt++;
	}
	printf("%d", cnt);
	return 0;
}

결과

맞으면 장땡