[백준 알고리즘] 소수 찾기(1978번) C로풀기

문제 이름 : 소수 찾기

문제 번호 : 1978

사용 언어 : C

문제 유형 : 완전 탐색

 

문제는 다음과 같다.

빈 배열을 만든 뒤 제시된 원소를 넣고 소수의 개수를 세면 된다.

이때 소수를 판별하는 방법으로는 두가지 방법을 같이 쓸 것이다.

 

1. 숫자가 2 또는 3인가?

2. 숫자 보다 작은 수들중 나눈 값의 나머지가 0인 수가 있는가?

 

2번 조건을 조금만 더 생각해보면 다음과 같은 결론에 도달할 수 있다.

소수가 아닌수는, 제곱근의 값을 중심으로 앞 뒤에 나누는 수가 존재한다는 것.

 

예를 들어보면 다음과 같다.

 

36 의 약수 - 1 2 3 4 6 9 12 18 36

제곱근인 6을 전후의 값을 곱한다는 것을 알 수 있다.

따라서 1부터 제곱근 값 사이에서 원래 수를 나눌 수 있는 수가 없다면, 그 수는 소수이다.

 

코드는 다음과 같다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h> // sqrt함수를 사용하기 위해
int main(){
    int yu1[100], num;
    int cnt = 0;
    scanf("%d", &num);
    for (int i = 0; i < num; i++) // 배열에 값 집어넣기
        scanf("%d", &yu1[i]);

    for (int i = 0; i < num; i++) { // 배열의 넣은 값들을 돌아보며 소수 판별중
        if (yu1[i] == 2) // 2는 소수이므로
            cnt++;
        else if (yu1[i] == 3) // 3역시 소수이므로
            cnt++;
    for (int k = 2; k <= sqrt(yu1[i]); k++) {  // 제곱근 까지의 수들 확인
        if (yu1[i] % k == 0)  // 나눠지면
            break;
        else if (k + 1 > sqrt(yu1[i])) // 나눠지지 않고 끝까지 도달했다면
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}