[알고리즘] 소수를 구하자 (소수#1)

2009. 05. 08 (金)

수학시간에 배운 소수(prime number)의 사전적인 의미는 1보다 큰 정수 p가 1과 p자신 이외의 양의 약수를 가지지 않을 때의 p를 소수라 정의합니다. 반대로 다른 숫자의 곱으로 이루어진 소수가 아닌 자연수를 합성수라 합니다.  참고로 1은 소수도 합성수도 아닙니다.

 

 

1.     자연수 n 의 소수 판단법

①     1부터 n까지 반복해서 n의 약수인지 확인한다.

②     만약 새로운 약수를 찾으면 count 변수를 +1한다

③     모든 확인이 끝난 뒤 약수의 개수가 2이면  소수이고 그렇지 않으면 소수가 아니다

 

2.     소스

#include "stdafx.h"

#include <stdio.h>

          

bool IsPrimeNumber(int n);

int _tmain(int argc, _TCHAR* argv[])

{

        int n = 0;

        printf("수입력: ");

        scanf("%d", &n);

 

        if(IsPrimeNumber(n) == true)

        {

               printf("소수\n");

        }

        else

        {

               printf("합성수\n");

        }

 

 

        return 0;

}

 

bool IsPrimeNumber(int n)

{

        int nCount = 0;

        for(int i=1 ;i <= n ; i++)

        {

               if(n%i == 0)

                       nCount++;

        }

 

        if(nCount == 2)

        {

               return true;

        }

 

        return false;

}