[C언어] 소수 판단 프로그램 예제 소스(prime number)

[C언어] 소수 판단 프로그램 예제 소스(prime number)

소수(prime number)는 무엇인가요?

소수(prime number)란 1과 자기 자신만으로 나누어지는 1보다 큰 양의 정수를 말합니다.

예를 들면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,… 등 1과 자기 자신만으로 나누어지므로 모두 소수라고 말할 수 있습니다.

4=(22), 6=(2×3), 16=(24)… 등, 소수가 아닌 자연수를 합성수(合成數)라 하며, 1은 소수도 아니고 합성수도 아닙니다.

소수인지 아닌지 어떻게 판단할까요?

자연수 n이 소수인지 아닌지를 판정하려면, 2≤p≤ (n/2)인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어지지 않는 수를 구하면 됩니다.

 

소수인지 판단하는 함수

소수인지 판단하는 함수를 C언어로 구현한 소스를 살펴 보겠습니다.

/*
========================================
# Function isPrime
----------------------------------------
입력 :
@ int number : 소수 여부를 판단할 숫자

반환 :
TRUE : number가 소수임
FALSE : number가 소수가 아님
----------------------------------------
*/
int isPrime( int number )
{
	int i = 0 ;

    // 2부터 입력받은 수(number/2)까지 반복
    for( i = 2 ; i <= (number/2) ; i++)
    {
        // 나누어 떨어지면 FALSE 리턴
        if ( number % i == 0 )
		{
			return FALSE;
		}		
    }

	// 나누어 떨어지지 않을 경우 소수임
	// TRUE 리턴
    return TRUE ;
}

소수 판단 예제 소스를 봅시다

다음은 입력받은 수가 소수인지 판단하는 C언어 예제 소스입니다.
오른쪽 상단의 툴바 버튼를 클릭하면 소스를 복사하실 수 있습니다. 주석을 자세하게 달았기 때문에 모르시는 분들도 쉽게 하실 수 있을 것입니다

#include<stdio.h>

// 상수 정의
const int FALSE = 0 ;
const int TRUE  = 1 ;

int isPrime( int number );

int main(int argc, char* argv[])
{
    int number = 0 ;
    int result = 0 ;

    printf("***** 소수 구하기 프로그램 *****\n") ;

	// 소수를 구할 숫자 입력
    printf("숫자를 입력하세요.\n==> ") ;
    scanf("%d", &number ) ;

	// isPrime(number)의 결과를 result에 대입
	result = isPrime(number);

	// result값으로 소수 여부 출력
	// result = TRUE일 경우 소수
	// result = FALSE일 경우 소수가 아님
	if ( result )
		printf("%d(은)는 소수입니다.\n", number);
	else
		printf("%d(은)는 소수가 아닙니다.\n", number);

	return 0;
}

/*
========================================
# Function isPrime
----------------------------------------
입력 :
@ int number : 소수 여부를 판단할 숫자

반환 :
TRUE : number가 소수임
FALSE : number가 소수가 아님
----------------------------------------
*/
int isPrime( int number )
{
	int i = 0 ;

    // 1인 경우 소수가 아니므로 FALSE 리턴
    if ( number == 1 )
        return FALSE;

    // 2부터 입력받은 수(number/2)까지 반복
    for( i = 2 ; i <= (number/2) ; i++)
    {
        // 나누어 떨어지면 FALSE 리턴
        if ( number % i == 0 )
		{
			return FALSE;
		}		
    }

	// 나누어 떨어지지 않을 경우 소수임
	// TRUE 리턴
    return TRUE ;
}

실행화면

위의 소스를 실행하면 아래와 같이 실행되는 것을 확인하실 수 있습니다.