[태그:] <span>1부터 1000 사이에 소수 찾기</span>

안녕하세요. 언제나 휴일입니다.

이번에는 1에서 1000사이의 정수 중에서 소수(Prime Number, 약수가 1과 자기 자신인 수)를 판별하여 출력하는 소스 코드입니다.

여기에서 사용하는 알고리즘은 가장 단순한 방법으로 반복문을 사용하고 있습니다.

알고리즘

소수인지 판별(num)

    조건(num is less than or equal to 1)

        거짓 반환

    반복(i:2->num)

        조건( (num%i) is equal 0)

            거짓 반환

    참 반환

소스 코드

//소수(Prime Number)인지 판별
#include <stdio.h> 

//함수명: IsPrimeNumber
//입력 인자로 전달받은 n이 소수인지 확인하는 함수
//반환값0: 소수가 아님
//반환값1: 소수임
int IsPrimeNumber(int n);  //함수 선언문


int main(void)
{
    int i = 0;
    for (i = 1; i <= 1000; i++) //i를 1부터 1000까지 1씩 증가시키며 반복 수행
    {
        if (IsPrimeNumber(i)) //i가 소수라면
        {
            printf("%3d ", i); //i를 출력
        }
    }
    printf("\n");
    return 0;
}

//함수명: IsPrimeNumber
//입력 인자로 전달받은 n이 소수인지 확인하는 함수
//반환값0: 소수가 아님
//반환값1: 소수임
int IsPrimeNumber(int n) //함수 정의문
{
    int i = 0;
    int last = n / 2;   //약수가 없는 수가 소수이므로 2부터 n/2(자기자신/2)까지만 확인하면 됨
    if (n <= 1)//소수는 1보다 큰 자연수여야 함
    {
        return 0;
    }
                        //(자기자신/2)보다 큰수는 약수가 될 수 없음
    for (i = 2; i <= last; i++) //i를 2부터 last까지 1씩 증가시키며 반복 수행
    {
        if ((n%i) == 0) //n을 i로 나누었을때 나머지가 0이면(즉, i는 n의 약수가 아님)
        {
            return 0; //소수가 아니므로 0반환(i가 약수이므로 n은 소수가 아님)
        }
    }
    return 1; //1~last(자기자신/2)사이에 약수가 없으므로 소수임
}

num의 약수 중에 num/2보다 큰 수가 없다는 특징을 이용하면 다음처럼 수정할 수 있어요.

/* https://ehpub.co.kr
 언제나 C언어 예제 Center
 소수(Prime Number)인지 판별
 */

#include <stdio.h>
int IsPrimeNumber(int num);
int main()
{
    int i = 1;
    int cnt = 0;
    for (i = 1; i <= 1000; i++)
    {
        if (IsPrimeNumber(i))
        {
            printf("%3d ", i);
            cnt++;
            if (cnt == 10)
            {
                printf("\n");
                cnt = 0;
            }
        }
    }
    printf("\n");
    return 0;
}
int IsPrimeNumber(int num)
{
    if (num <= 1)
    {
        return 0;
    }
    int half = num / 2;
    for (int i = 2; i <=half; i++)
    {
        if (num%i == 0)
        {
            return 0;
        }
    }
    return 1;
}