[C언어] CHAPTER 07 반복문 / Programming 07 / 2와 100 사이에 있는 모든 소수를 찾는 프로그램

 

정수가 소수가 되려면

1과 자기 자신만을 약수로 가져야 한다.

 

약수란, 정수를 나누었을 때 나머지가 0이 되는 것이다.

즉,

정수 / N = 약수, ( 8 / 2 = 4 ) <-- 이 때, 2도 8의 약수이다.

정수 % 약수 = 0, ( 8 % 4 = 0 )

약수 * N = 정수가 성립하면 되는 것이다. ( 4 * 2 = 8 )

즉 임의의 정수가 약수의 배수가 되는 관계이다.

 

2 x 4 = 8의 경우,

8의 약수는 2도 되고 4도 된다.

설명이 잘 되었는지는 모르겠지만..

잘 모르겠다면 약수를 검색하여

소인수분해의 개념부터 익히길 바란다.

 

이 포스팅의 제목 조건에 부합하는

소수 프로그램을 작성해 보았다.

 

 

#include <stdio.h>
 
int main(void)
{
    int number = 2; // 임의의 정수, 소수를 찾을 정수
 
    int i = 2, count = 0; // i는 반복 변수이며, count는 약수의 개수를 체크
 
    for (number = 2; number <= 100; number++)
    {
        for (i = 2; i <= number; i++)
        {
            if (number % i == 0) 
                count++;
        }
 
        if (count == 1)
        {
            printf("%d ", number);
        }
    }
 
    return 0;

  - 설명  

( ★ 코드에 논리적 오류 발생 주의! )

 

중첩 반복문을 활용하였다.

 

임의의 정수(소수를 찾는 범위의 정수)는

2부터 100까지 증가하며,

1과 자기 자신만을 약수로 가지는 것이 소수이므로

나누어 주는 수 i의 범위는 2부터 number까지로 설정한다.

(정수가 5인데 5를 초과하여 나누는 것은 무의미하므로.)

 

나누는 수는 1을 포함해도 되긴 하지만

모든 수는 1의 배수,

즉 1은 모든 수의 약수이므로

효율성이 떨어진다고 판단되어

정수를 2부터 자기자신까지 나눈 후,

나머지가 0이 될 때 count를 1 증가시키고,

내부의 for문이 다 반복되고 number가 다음 수로 변경되기 전에

count가 1인 것(자기 자신으로만 나누어 떨어진 것)

을 찾아 소수로 판단하고 출력하였다.

 

 

하지만 결과는 다음과 같았다.

 

 

 

??????????????

무엇이 문제인지 확인하기 위해,

number의 약수의 개수를 다 찾은 후인

16번째 줄에 아래 코드를 삽입하였다.

 

printf("%d, %d\n", number, count);

보자마자 coun

t 변수가 초기화 되지 않아

number가 2일 때도, 100일 때도

count가 증가하고 있기 때문에

count == 1이 되는 수가 2뿐이라는 것을 깨달았다.

 

22번째 줄에(내부 for문이 다 끝나는 줄)

count를 0으로 초기화시켜 주니,

 

 

정상적으로 소수가 출력되었다.

 

 

 

 

  - 한마디  

컴파일러가 잡아내지 못하는

논리적 오류는 언제, 어디서나 발생할 수 있다.

 

이런 중첩 반복문 같은 경우,

printf문으로 변수나 결과값 등을

중간중간에 넣어

어떤 소속의 반복문이나 구역에서

오류가 발생하였는지 꼼꼼히 찾아보고

수정하는 것도 좋은 방법인 것 같다.