Baekjoon Online Judge _ 01978 _ 소수 찾기

[ Baekjoon Online Judge _ 01978 _ 소수 찾기 ]

문제

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

입력

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

출력

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

예제 입력

4
1 3 5 7

예제 출력

3

풀이

C로 풀어본 소수찾기 알고리즘

중고등학교 때 배웠던 에라토스테네스의 체를 코드로 구현했다!

문제에서 1000이하의 자연수까지만 고려하므로

크기가 1001인 배열을 만든다. (인덱스와 숫자를 일치시키기 위해서)

1은 소수가 아니므로 제외하고

2부터 차례로 배수를 지워나간다.

이 때 1000의 제곱근까지만 계산하면 된다.

1000을 어떤 숫자로 나누더라도 제수, 피제수중 하나는 1000의 제곱근보다 작기 때문이다.

사실 처음에는 배수를 지워나갈 때 % 연산자를 사용했는데

i의 배수는 i를 계속해서 더해나가면 된다는 걸 깨닫고 수정했다!

% 연산자는 연산속도가 느리기 때문에 i 를 더해가는 방식이 더 효율적이다.

코드

#include <stdio.h>
#pragma warning(disable:4996)
 
#define MAX 1000
#define FALSE 0
#define TRUE 1
 
int main() {
    int N = 0; // 100이하
    int num;   // 입력받을숫자
    int count = 0; //소수 개수
    int prime_number[MAX + 1];  //배열인덱스와 숫자를 일치시키기 위해 크기를 1 늘림
 
    //배열 초기화
    prime_number[1] = FALSE; //1은소수가아님
    for (int i = 2; i <= MAX; i++) 
        prime_number[i] = TRUE; //먼저 모두 TRUE로 초기화
 
    //소수가 아닌 것을 찾아 하나씩 FALSE로 지워나감
    for (int i = 2; i*i <= MAX; i++) {
        if (prime_number[i] == TRUE) {
            for (int j = i*i; j <= MAX; j += i) {
                prime_number[j] = FALSE;
            }
        }
    }
 
    scanf("%d", &N);
    while (N--) {
        scanf("%d", &num);
        if (prime_number[num] == TRUE)count++;
    }
 
    printf("%d", count);
    return 0;
}