C언어- 소수 판별 예제

문제

 자연수 A가 소수인지 아닌지 판별하는 코드를 작성하세요.

위 문제를 해결하기 위해 우선 소수의 정의에 대해 살펴보겠습니다.

소수란?

 - 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. [출처1]

 - 즉, 약수가 2개인 1보다 큰 자연수

다음으로 약수의 정의에 대해 살표보겠습니다.

약수란? 

 - 두 정수 , 에 대하여 를 만족하는 정수 가 존재한다면, 를 의 약수라고 한다. [출처2]

 - 즉, 를 로 나누었을 때 나머지가 0이면, 를 의 약수라고 한다.

소수 판별 예제를 반복문으로 해결하기 위해 다음 3가지를 정리해야 합니다.

1. 반복횟수 : 초기화, 조건식, 증감연산식을 결정

2. 규칙성 : 실행문을 결정

3. 반복문 종료 후 작업

1. 반복횟수

 - 자연수 A가 소수인지 판별하기 위해서는 A의 약수를 찾아야 합니다. 

 - 즉, 1과 A사이에 있는 모든 자연수를 A로 나누어서 나머지가 0인지 확인해야합니다.

 - 따라서 반복횟수는 1부터 A까지 1씩 증가해야합니다.

 - 초기화 : i = 1

 - 조건식 : i <= A

 - 증감연산식 : i++ 또는 ++i 또는 i+=1

2. 규칙성 

 - 1과 A사이에 있는 자연수가 i라 할 때, i가 A의 약수이면 약수의 갯수를 증가시켜야 합니다.

 - 즉, A를 i로 나누었을 때 나머지가 0과 같다면 약수의 갯수를 증가시킵니다.

 - 조건식 : A를 i로 나누었을 때 나머지가 0과 같다 => A % i == 0

 - 조건식 실행문 : 약수의 갯수를 증가 => count++

3. 반복문 종료 후 작업

 - 반복문 종료 후 약수의 갯수가 2개이면 소수라고 출력합니다.

 - 반복문 종료 후 약수의 갯수가 2개가 아니면 소수가 아니라고 출력합니다.

 - 조건식 : 약수의 갯수가 2개이다 => count == 2

 - 조건식 실행문 : 소수라고 출력

 - else문 실행문 : 소수가 아니라고 출력

정리한 내용을 바탕으로 소수 판별 예제 코드는 아래와 같습니다.

#include <stdio.h>
 
int main() {
    //자연수 A
    int A = 6;
    //약수의 갯수
    int count = 0;
    //반복문에서 사용할 변수
    int i;
    for (i = 1; i <= A; i++) {
        if (A % i == 0) {
            count++;
        }
    }
    if (count == 2) {
        printf("%d는 소수입니다.\n", A);
    }
    else {
        printf("%d는 소수가 아닙니다.\n", A);
    }
    return 0;
}

질문은 댓글로 남겨주세요.

출처

출처1. 위키백과, “소수(수론)”, 위키백과 , https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

출처2. 위키백과, “약수”, 위키백과 , https://ko.wikipedia.org/wiki/%EC%95%BD%EC%88%98#%EC%A0%95%EC%9D%98