[C] C study mini project: 함수 - 소수 출력 프로그램

[C] C study mini project: 함수

 

 

 

---

[1] 문제

 

문제 설명

소수인지를 검사하는 함수 check_prime()를 사용하여 1부터 100사이에 존재하는 소수들을 모두 출력하는 프로그램을 작성해보자.

 

입출력 예시

 

 

 

---

[2] 정답

 

#include <stdio.h>
 
int check_prime(int num) {
    int i;
    
    if (num <= 1)
        return 0;  // 1 이하의 숫자는 소수가 아님
    
    for (i = 2; i < num; i++) {
        if (num % i == 0)
            return 0;  // 나누어떨어지는 숫자가 있으면 소수가 아님
    }
    
    return 1;  // 소수임
}
 
int main() {
    int i;
    
    printf("1부터 100사이의 소수들:\n");
    
    for (i = 1; i <= 100; i++) {
        if (check_prime(i))
            printf("%d ", i);
    }
    
    printf("\n");
    
    return 0;
}

 

 

 

---

[3] 해석

 

이 코드는 1부터 100 사이의 소수를 찾아서 출력하는 프로그램이다.

 

 

1. 소수(Prime Number)란 무엇인가?

소수는 1과 자기 자신 이외의 양의 정수로 나누어떨어지지 않는 수를 말한다.

즉, 약수가 1과 자기 자신만 있는 수를 소수라고 한다.

예를 들어, 2, 3, 5, 7, 11, 13 등이 소수에 해당합니다.

 

 

2. 소수 판별 방법:

우리가 어떤 숫자를 소수인지 아닌지 판별할 때, 그 숫자의 제곱근까지만 확인하면 충분하다.

예를 들어, 100을 소수인지 판별하려면 10까지만 확인하면 된다.

 

이유는 간단하다. 어떤 숫자가 소수가 아니라면, 반드시 그 숫자의 약수가 될 수 있는 숫자는 제곱근을 기준으로 대칭성을 가지기 때문이다.

 

예를 들어, 100을 예로 들면:

 

1은 100의 약수이다. (100 ÷ 1 = 100)

2도 100의 약수이다. (100 ÷ 2 = 50)

4도 100의 약수이다. (100 ÷ 4 = 25)

5도 100의 약수이다. (100 ÷ 5 = 20)

10도 100의 약수이다. (100 ÷ 10 = 10)

20도 100의 약수이다. (100 ÷ 20 = 5)

25도 100의 약수이다. (100 ÷ 25 = 4)

50도 100의 약수이다. (100 ÷ 50 = 2)

 

이렇게 약수는 항상 제곱근을 기준으로 대칭성을 가진다. 그렇기 때문에 우리는 제곱근까지만 확인하면 된다.

100의 제곱근은 약 10이다. 따라서 100이 소수인지 판별할 때는 2부터 10까지만 확인하면 된다.

만약 10보다 큰 약수가 있다면, 그 약수의 하나는 반드시 10보다 작은 값이 될 것이다. 예를 들어, 100의 약수 중 20이라면, 다른 약수 중 하나는 5가 될 것이다. 하지만 5는 이미 10보다 작은 값으로 확인한 약수 중에 있다.

 

따라서 불필요한 계산을 피하면서도 제곱근까지만 확인하면 모든 약수를 판별할 수 있다. 이 방법을 사용하면 소수를 더 효율적으로 찾을 수 있다.

 

3. check_prime 함수:

• 이 함수는 주어진 숫자 num이 소수인지 아닌지를 판별하는 역할을 한다.
• num이 1보다 작거나 같으면 0을 반환하여 소수가 아니라고 처리한다. (1 이하의 숫자는 소수가 아님)
• 그렇지 않은 경우에는 for 루프를 통해 i가 2부터 num 이전까지의 숫자들로 나누어 떨어지는지 확인한다.
• 만약 num이 i로 나누어 떨어지면 0을 반환하여 소수가 아니라고 처리한다. (나누어떨어지는 숫자가 있으면 소수가 아님)
• for 루프를 모두 돌았는데도 위 두 경우에 해당하지 않으면 1을 반환하여 소수임을 알려준다.

 

 

4. main 함수:

• 이 함수는 프로그램의 진입점이다.
• i 변수를 선언하여 1부터 100까지의 숫자를 하나씩 증가시키면서 소수인지 check_prime 함수를 호출하여 판별한다.
• 소수인 경우 해당 숫자를 출력한다.

 

5. C 언어와 소수 관련 함수:

C 언어에서는 소수를 다루기 위해 math.h 라이브러리에 소수 관련 함수가 포함되어 있지는 않는다.

따라서 직접 소수를 판별하는 함수를 작성해야 한다.

 

 

---

[4] 풀이 및 오답

 

 

 

---

[5] 추가 학습

 

✏️ math.h 라이브러리란?

https://exponent.tistory.com/66

[C] math.h 라이브러리

 

 

 

---

[6] 느낀 점

 

✏️ 함수는 이미 만들어져 있는 것을 호출해서 사용한다!!!!!! 기본의 기본의 기본적인 이야기...

 

✏️ 소수를 판별할 때는 직접 코드를 작성해야 하지만, math.h 라이브러리를 이용하면 다양한 기능을 사용할 수 있다는 것을 알았다. 직접 사용해보는 내용의 글도 다음에 작성해야지!

 

✏️ 알고리즘을 잘 짜려면... 반복문도 잘 알아야 하고 함수도 이해해야하고... 공부 열심히 해야겠다...