c언어 러시아 농부 곱셉 알고리즘, 농부곱셈법, 이집트곱셈법

'a la russe' 알고리즘이라고도 불린다. 

알고리즘을 살펴보자면

1. 곱하고 싶은 두 수 A, B를 입력한다.

2. A를 2로 나누고 몫만 취하고 나머지는 버린다.

3. A를 나눈만큼 B도 2씩 곱한다.

4. 이 과정을 A를 더 나눌 수 없을때 까지 반복 (몫이 1일때까지 반복)

5. A를 나눈 몫이 홀 수 일 경우의 B의 값을 다 더한다.

이것을 c언어 코드로 보자면 

#include <stdio.h>
 
main() {
    int A, B, result = 0; //A, B와 result 결과값
    scanf("%d %d", &A, &B); //입력
    while (A >= 1) { //A의 몫이 1일때 까지만반복
        if (A % 2 == 1) //A가 홀수면 
            result += B; //result에 B를 더한다.
        A /= 2; //A는 2로 나눈 몫만 저장
        B *= 2; //B는 2배
    }
    printf("%d \n", result);
}