[알고리즘]C언어 약수의 개수 /약수의 개수 알고리즘

예전 티스토리 블로그를 할 때, 작성했던 적이 있는데 다시 한번 정리해보려고 합니다.

 

C언어로 약수의 개수를 구할 때, 가장 선행되어야 하는 것은 손으로 약수의 개수를 구하는 풀이법을 알고 있어야 합니다.

 

최대한 쉽게 설명해볼께요

 

자 따라오세요!

 

우선 약수란 나누어 떨어지는 수를 얘기합니다. 즉, 나눴을 때 나머지가 없는 수를 말해요!

 

4는 1로 나누면 나누어 떨어지고, 2로 나누어도 나누어 떨어지고, 3은 안되고 4는 됩니다.

 

3은 1로 나누면 나누어지고, 2는 안되고, 3은 되죠

 

네 맞습니다. 이처럼 나누어 떨어지는 수를 약수라고 부릅니다.

 

촉 빠르신 분들은 이미 눈치채셨겠죠!?

 

1은 모든수의 약수가 됩니다. 무조건이죠

 

자연수중 1로 안나눠 떨어지는 수는 없으니까요.

 

그리고 수 자기자신도 자신의 약수가 됩니다.

 

3을 3으로 나눠도 나눠떨어지죠?

 

78951을 78951로 나누면 몫이 1이 되고 나머지가 0이 되니까 나누어 떨어지는거요 ㅎㅎ

 

이처럼 모든 수는 1과 자기자신의 수로 나눠집니다.

 

여기서 1과 자기자신으로만 나누어지는 수를 "소수"라고 부르는 거구요.

(사실 소수, 약수, 소인수분해 구하는 알고리즘이 다 비슷합니다.)

 

왜 자꾸 수학 얘기만 하는거지 하시는분들이 있을까봐 ㅎㅎ;;

사실 프로그래밍은 이런 수학적 혹은 반복적인 일을 하기 쉽게 만들어 놓게 프로그램화시켰다고 봐야합니다.

그러니까 본질적인것을 알아야 코딩할 때 막히지 않고 만들 수 있어요

 

약수의 개수 공식은 아래와 같습니다.

 

약수의 개수를 구하는 공식

조금 사족을 붙인다면, 2, 3, 5, 7로 더이상 안나눠질때까지 나누는 행위! 를 했을 때

1을 제외한 나오는 몫의 (지수+1)한 값들을 모조리 곱해주면 됩니다.

 

이해가 안되시면 2, 3, 5, 7로 일단 나누세요 ㅋㅋ

예를 들어 보겠습니다.

10이 있습니다.

10 / 2 = 몫 : 5, 나머지 = 0 [나누어진다.]

(이제 10이 아니라 나온 몫인 5를 가지고 진행)

5 / 2 => 나눠지지 않음, 패스!

5 / 5 => 몫 : 1, 나머지 = 0 [나누어진다.]

몫이 1이 되면 더이상 나눠지지 않기때문에 종료입니다.

 

그림으로 표현하면

2 |10

5 | 5

1

이렇게 되겠죠 !?

(사실 그림아니라 밑줄긋고 만든거;;;헐 블로그에 수식 쓸 수 있는 방법이 있나요 ?)

 

결국 10 = 2 X 5 X 1로 표현이 되죠 ?(왼쪽 모두와 최하단의 곱)

결국 2의 1승, 5의 1승, 1의 1승으로 표현이 됩니다.

 

이제 나온 값에서 1을 제외한 값들의 지수들에 1을 더하세요

그러면

2의 1승이니까 (1+1) = 2

5의 1승이니까 (1+1) = 2

 

그리고 그 값들을 곱해주면 2X2 = 4

즉, 10의 약수의 개수는 4개가 됩니다!!!

10은 수가 작으니까 바로 검증할 수 있죠 ㅋㅋ

10의 약수 : 1, 2, 5, 10 오 맞습니다 ㅎㅎ

 

빠르게 100을 예로 한번 더 해볼께요

2 |100

2 | 50

5 | 25

5 | 5

1

 

즉 100 = 2의 2승 X 5의 2승

약수의 개수는 (2+1) X (2+1) = 3 X 3 = 9

직접 검증해보면

100의 약수 : 1, 2, 4, 5, 10, 20, 25, 50, 100 ====> 9개 입니다.

 

그럼 본격적으로 위의 내용을 C언어로 프로그래밍 해볼께요.]

자 C언어로 구현한 약수의 개수 구하는 전체 소스입니다.

#include <stdio.h> void main() { int input_number; printf("약수를 구할 수를 입력하세요 : "); scanf("%d", &input_number); divisor(input_number); } int divisor(int number) { int input_number = number; int count_2 = 1; int count_3 = 1; int count_5 = 1; int count_7 = 1; int result; while(1) { if(input_number == 1 || (input_number % 2 != 0 && input_number % 3 != 0 && input_number % 5 != 0 && input_number % 7 != 0)) { break; } else { if(input_number % 2 == 0) { count_2 += 1; //count_2 = count_2 + 1; 과 동일 input_number /= 2; //input_number = input_number / 2; 와 동일 continue; } else if(input_number % 3 == 0) { count_3 += 1; input_number /= 3; continue; } else if(number % 5 == 0) { count_5 += 1; input_number /= 5; continue; } else if(number % 7 == 0) { count_7 += 1; input_number /= 7; continue; } } } if(input_number == 1) { result = count_2 * count_3 * count_5 * count_7; } else { result = count_2 * count_3 * count_5 * count_7 * 2; } printf("%d의 약수의 개수 : %d\n", number, result); }

 

복붙이 안되시면 아래 텍스트파일 받으시고 복붙하세요!

manniz_al_001.txt

 

한번 쭉 훝어보세요! 밑에 설명도 써놓을 께요.

그런데 먼저 보면서 생각하는게 공부에 도움이 많이 됩니다.

일단 메인문 입니다!

#include <stdio.h> void main() { int input_number; printf("약수를 구할 수를 입력하세요 : "); scanf("%d", &input_number); divisor(input_number); }

메인문은 간단합니다.

1. int형 변수 input_number 선언해주고,

2. printf로 숫자 입력하라는 메시지 표출

3. scanf로 위에 선언한 input_number에 값을 넣은거죠

※scanf("자료형", 변수의주소); %d는 정수형, 변수명에 "& "이게 붙으면 c에서는 해당변수의 주소를 알려줘요.

즉 scanf라는 것은 해당변수의 주소에 값을 넣을 건데 정수형으로 넣을꺼야 라고 하는거죠

 

4. divisor라는 함수를 호출하는데, 파라미터로 input_number, 즉 입력받은 값을 던져줍니다.

 

잘따라오고 계신가요!?!??!

솔직히 메인문에서는 하는게 없습니다...

 

그럼 이제 실제 약수의 개수를 구하는 divisor함수를 보죠

다음은 변수 선언 부분이예요

int input_number = number; int count_2 = 1; int count_3 = 1; int count_5 = 1; int count_7 = 1; int result;

우선 변수를 선언했습니다.

input_number는 파라미터로 반은 값을 넣어줍니다. 즉 우리가 키보드로 입력한 값이죠

count_2, count_3, count_5, count_7은 지수의 개수를 의미합니다.

result는 제일 마지막에 결과값을 출력해주기 위해서 만든 변수입니다.

while(1) { if(input_number == 1 || (input_number % 2 != 0 && input_number % 3 != 0 && input_number % 5 != 0 && input_number % 7 != 0)) { break; }

1. while문은 아시죠!? 반복하라라는 건데, c에서는 1을 true라고 인식을 합니다. 즉 저말은 while문 안의 행동을 계속 무한히 반복해라라는 거죠. 흔히 무한루프 빠졌다는 말 많이 하잖아요 바로 그 무한루프 입니다 ㅋㅋ 하지만 그 밑의 if문을 통해서 빠져나올수가 있습니다.

 

2. if(input_number == 1 || (input_number % 2 != 0 && input_number % 3 != 0 && input_number % 5 != 0 && input_number % 7 != 0))

if조건문 인데요. 여기가 거의 핵심이라고 볼수 있습니다. 저걸 음 말로 풀어보면

(지금 계산해야하는 값이 1이거나) (2로 나눠지지 않으면서 3으로 나눠지지 않으면서 5로 나눠지지 않으면서 7로 나눠지지 않으면)

이 말은 즉, ==> 더 이상 나눠지지 않을 때!!!를 의미합니다.

결국 더이상 나눠지지 않으면

break; 명령어를 실행해

라는 말을 c언어로 구현한 거예요.

break문은 현재 실행중인 구문을 끝내고 다음 스텝을 진행하는 c언어 명령어입니다.

자 계속 보시죠!

else { if(input_number % 2 == 0) { count_2 += 1; //count_2 = count_2 + 1; 과 동일 input_number /= 2; //input_number = input_number / 2; 와 동일 continue; }

else문이 나왔네요. 위의 if문 의미가 결국은 더이상 나눠떨어지지않을때 였으니까

그렇지 않다는것은 !!

나눠질때 라는 의미겠죠!

그럼 나눠지는 경우에는 어떤 처리를 하나 보죠

 

위 코드의 의미를 또 말로 풀면

음 들어온 숫자가 2로 나눠져?

A) 나눠진다 --> 2의 지수값에 1을 더해, 다음 계산해야 할 값을 2로 나눠, while문의 처음으로 돌아가

continue : 해당 구문을 처음부터 다시 시작하게 합니다.

B) 안나눠진다 --> 그냥 패스 ㅋㅋ

이런 뜻입니다.

else if(input_number % 3 == 0) { count_3 += 1; input_number /= 3; continue; } else if(number % 5 == 0) { count_5 += 1; input_number /= 5; continue; } else if(number % 7 == 0) { count_7 += 1; input_number /= 7; continue; } } }

 

이걸 3으로 나눠져? 라고 물어보고

5로 나눠져?

7로 나눠져 ?

이런식으로 계속 물으면서 진행하는거예요.

 

결국 안나눠질때까지 2, 3, 5, 7로 나누고

2로 나눠졌으면 2의 지수에 +1, 하고 계산해야할 값을 2로 나눈 몫을 다시 계산 !

3으로 나눠졌으면 3의 지수에 +1, 하고 계산해야할 값을 3로 나눈 몫을 다시 계산 !

5로 나눠졌으면 5의 지수에 +1, 하고 계산해야할 값을 5로 나눈 몫을 다시 계산 !

7로 나눠졌으면 7의 지수에 +1, 하고 계산해야할 값을 7로 나눈 몫을 다시 계산 !

 

더이상 안나눠 지면 while문을 빠져 나오게 됩니다.

if(input_number == 1) { result = count_2 * count_3 * count_5 * count_7; } else { result = count_2 * count_3 * count_5 * count_7 * 2; } printf("%d의 약수의 개수 : %d\n", number, result); }

무한 반복문을 빠져나왔으면 결과 출력을 위해서 값을 계산합니다.

그런데 여기서 경우의 수가 2가지가 나옵니다.

A) 전부다 나눠진 경우

B) 나눠떨어지지않은경우

 

A의 경우는 2, 3, 5, 7의 지수만을 보면 됩니다.

예를 들어 6같은 경우

2X3으로 표현이 되고, 위의 값을 적용해보면

2(2의지수+1) X 2(3의지수+1) X 1(5의지수+1) X 1(7의지수+1) = 4가 되죠!

5, 7은 계산에 포함이 안되어서 지수값이 0(모든 정수의 0승 = 1)이어서 (0+1)이 된거예요.

 

B의 경우는 다 나눠지지 않은 경우입니다.

네 맞아요 소수에서 이런 경우가 생깁니다.

13을 예로 들어볼께요

13은 2, 3, 5, 7 어느 경우에도 나눠지지 않습니다.

즉 어떠한 수도 계산에 포함이 안되었죠

그런데 A와 같이 적용해 버리면 값이 1이 나와요

사실은 1, 13으로 약수가 있는데 말이죠

그래서 그 처리를 한거예요

 

실제 프로그램을 돌려서 결과를 확인해보면

 

10의 약수의 개수 테스트

 

 

7의 약수의 개수 테스트

 

 

392의 약수의 개수 테스트

 

 

15487932의 약수의 개수 테스트

 

요렇게 나옵니다.

 

하...가벼운 마음으로 포스팅을 시작했는데 길어졌네요...

-_-;;;

 

프로그램도 블로그 글쓰면서 만들다 보니까 전혀 아름답지가 않네요 ㅠ_ㅠ

 

고생하셨습니다.

 

아! 혹시 몰라서 c파일도 첨부해 두도록 하겠습니다.

 

그럼 다음에 뵈요~~

 

manniz_algo_001.c