[50] C 백준 1978번 소수찾기 문제 (수학)

문제

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

입력

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

출력

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

예제 입력 1 

4
1 3 5 7

예제 출력 1 

3

 

 

<풀이>

소수를 찾는 알고리즘에는 여러가지가 있다.

(2부터 N -1 까지 확인하기, N / 2까지 확인하기, 루트N까지 확인하기 등)

https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

(위 블로그 참조)

 

숫자 N이 주어졌을 때  √N 까지의 약수를 확인하는 법이다. 

합성수 n이  p*q로 표현될 때 한 수는 항상 √N이하, 다른 한 수는 √N 이상이라는 점을 이용하면 n-1까지 순회하지 않고  √N까지만 순회하도록 최적화할 수 있다. (https://loosie.tistory.com/267) 참고

이 알고리즘을 이용할 경우 시간 복잡도는 O(N^1/2)이 된다.

 

<제출한 코드>

#include <stdio.h>

int primeCheck(int num){ // 소수인지 확인하는 함수
    if (num < 2) return 0;

    for (int i = 2; i * i <= num; i++){ // 루트num 까지만 확인. 시간복잡도 O(N^1/2)
        if (num % i == 0) return 0; // 소수가 아니면 0 리턴
    }
    return 1; 소수가 맞으면 1 리턴
}

int main(void){
    int testcase, arr[100] = {0, }, primeNum = 0;
    
    scanf("%d", &testcase);
    for (int i = 0; i < testcase; i++){
        scanf("%d", &arr[i]);
        primeNum += primeCheck(arr[i]); // 소수의 개수
    }
    printf("%d", primeNum);

    return 0;
}