티스토리 뷰



[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 ;
}


   실행화면


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



신고
댓글
댓글쓰기 폼
  • 강동균 틀리셨네요 1은 소수가 아닙니다. 2014.12.08 12:10 신고
  • 하늘과 나 제 글 중에 어디에 1은 소수라고 써있었나요? 2014.12.08 12:33 신고
  • ㅁㄴㅇㄹ 틀리신거 맞습니다. 돌려보니 1은 소수라고 나오네요. 1은 소수가 아닙니다.
    1은 소수도 합성수도 아니고 2부터 소수임을 판별 할 수 있습니다.
    예외처리를 안하셨네요.
    2014.12.22 13:50 신고
  • 하늘과 나 강동균님께서 처음에 글을 남겨주셨을 때는 제가 쓸 내용 중에 틀린 부분이 있는 줄 알았는데 소스에서 잘못된 부분이 있었군요.
    감사합니다. 수정했습니다.
    2014.12.22 18:58 신고
  • 궁금이 저 죄송한데
    소수를 판별하는 부분에서
    i <= (number/2)까지 수행하는 이유는 무엇인가요?
    다른 소스들에서는 i <= number 까지 검사하더라구요.
    무슨 성질이 있는건가요?
    2016.03.27 22:14 신고
  • 하늘과 나 소수는 1과 자신을 약수로 가지는 수죠.
    그렇기 때문에 2로 나눠져서는 안되요.

    4를 예로 들었을 때 약수는 1,2,4죠.
    6을 예로 들었을 때 약수는 1,2,3,6이죠
    10을 예로 들었을 때 약수는 1,2,5,10이죠

    절반까지만 계산해도 그 수가 소수인지 아닌지 알 수 있어요.

    그래서 number/2를 쓴거에요
    2016.03.27 23:32 신고
  • 궁금이 또 궁금한게 있는데요.
    i <= number/2 가 아니라
    i < number/2 까지만 하는건 어떤가요?
    2016.03.30 09:34 신고
  • 하늘과 나 그 방법도 괜찮을 것 같네요^^ 2016.03.30 10:13 신고
  • dkdkdk 그럼 4는 어쩌려고 ㅆㅂㅋㅋㅋㅋㅋㅋㅋ 2017.07.29 22:44 신고