c언어 소수 / c언어 소수 구하기 / c언어 Prime number / c언어 소수 소스

먼저 C언어 소수 소스 입니다.

#include <stdio.h>

 

/*

        소수를 출력하는 프로그램

        소수 : 1과 자기자신만을 약수로 갖는 수

*/

main()

{

       

        int num, count, count_all=0;

 

        printf("소수를 구하고 싶은 범위를 입력하세요 (1~입력값) : ");

        scanf_s("%d", &num);

        for (int i = 1; i <= num; i++) {

               count = 0;

               for (int j = 1; j <= i; j++) {

                       if (i%j == 0) {

                              count++;

                             

                       }

               }

               if (count == 2) {

                       printf("%d\n",i);

                       count_all++;

               }

                      

        }

        printf("1에서 %d까지 총 %d개의 소수가 있습니다.\n", num,count_all);

}

다음은 c언어 소수 구하기 결과 입니다.

c언어 소수 알고리즘 설명

우선 소수라는 것의 의미를 정확히 파악하는게 중요합니다.

소수라는 것은 1과 자기자신만으로 나누어지는 수 == 1과 자기 자신 이외에는 나누어지지 않는 수 입니다.

위의 소스는 이 점을 활용한 알고리즘을 사용하였습니다.

우선 구하고자하는 값의 상한선을 입력 받습니다(num)

이제 이 숫자까지 모든 수를 그 숫자 이하의 값으로 모두 나눠보는 것입니다.

나눈다는것이 /(divide)를 사용하는 것이 아니라 %(mod)를 통해서 나머지 값만 보면 됩니다.

나머지가 0 이라는 것은 나눠 떨어진다는 것 이기 때문에 이게 더 간단하죠

즉 모든수에 대입해본 결과 나머지가 0이 나온경우가 2번 이라는 것은 1과 자기자신밖에 없다는 것을 의미하죠 ?

c언어 소수 구하기 알로리즘 설명

ex)

2가 왔을 때

2/1의 나머지 = 0 (1은 모든 수의 약수) count = 1

2/2의 나머지 = 0  count = 2

따라서 2는 소수 입니다.

3이 왔을 때

3/1의 나머지 = 0 count = 1

3/2의 나머지 !=0 count = 1

3/3의 나머지 =0 count = 2

따라서 3은 소수

4가 왔을 때

4/1의 나머지 = 0 count = 1

4/2의 나머지 =0 count = 2

4/3의 나머지 !=0 count = 2

4/4의 나머지 =0 count = 3

즉 약수는 3개 -> 소수가 아님

count라는 변수는 곧 약수의 개수 입니다.

약수의 개수가 2개이다 = 약수가 1과 자기자신뿐이다 = 소수

이걸 이용하여 c언어 소수를 구하였습니다.

이상으로 C언어로 소수를 구하는 알고리즘 포스팅을 마치겠습니다.

감사합니다~