Korean, Edit

Finding consecutive natural numbers by using C language

Higher category : 【C language】 C language index

a. GitHub

Q. Find the number of ways to make a given number by summing up at least two consecutive natural numbers. For example,

15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

There are a total of four methods.

Lemma.

Let N be the given number, N = a × b, a = 2k form, and 2 does not divide b. Then, the number of ways demanded in the problem is equal to the number of divisors of b.

Proof.

Consider adding n to k natural numbers.

In this case, it can be seen that k is a divisor of 2N.

For any divisor k of 2N, let n be defined, and the following condition is necessary and sufficient.

Since 2n + k - 1 and k have different parities, if one side is an odd divisor of 2N, the other side is an even divisor. (Second condition)

First, let’s ignore the condition 2n + k - 1 > k and think about it.

2n + k - 1 can be even and k can be odd, or 2n + k - 1 can be odd and k can be even.

(Note that 2N is even.)

In each case, it can be easily confirmed that the number of ways is equal to the number of divisors of b.

However, since 2n + k - 1 and k have different parities, they cannot be equal.

Also, since 2n + k - 1 and k are symmetrical, the number of cases where 2n + k - 1 > k and k > 2n + k - 1 is the same.

Therefore, considering 2n + k - 1 > k, we have the following:

#include <stdio.h>
#include <stdlib.h>
/* This source applies integer factorization to get the number of divisors of a certain number */

int main(int argc, char *argv[]) {
	long long int n;
	scanf("%lld", &n);
	int Count_Divisor = 1;
	int i = 3;
	int count = 0;
    
	while(1){
		if(n % 2 == 1) break;
		n = n / 2;
	}
    
	while(1){
		if(n == 1){
			Count_Divisor = Count_Divisor * (count + 1);
			break;
		}
		if(n % i == 0){
                        count ++;
                        n = n / i;
                        i -= 2;
		}
		else{
			Count_Divisor = Count_Divisor * (count + 1);
			count = 0;
		}
		i += 2;
	}
	printf("%d", Count_Divisor);
	return 0;
}

Input: 2016.02.17 23:50