数値Xの約数を数える

元の記事とは関係ないけどおまけ

ループその１

何にもわからなかったら、まずは素朴に

int	divisors_count( int	a ){
	debug_printf( "{ " );
	int	result = 0;
	int	n = 1;
	while( n <= a ){
		if( !( a % n )){
			if( n > 1 ){
				debug_printf( ", " );
			}
			debug_printf( "%d"), n );
			++result;
		}
		++n;
	}
	debug_printf( " } ... " );
	return	result;
}

int	main(){
	for( int	n = 0; n < 60; ++n ){
		int	cdivisors = divisors_count( n+1 );
		debug_printf( "... %d の約数の数は %d個\n", n+1, cdivisors );
	}
	return	0;
}

ループその２

約数は必ずペアなので、それを考慮して

int	divisors_count( int	a ){
	int	result = 0;
	int	b = a;
	int	n = 1;
	do{
		if( !( a % n )){
			if( n > 1 ){
				debug_printf( ", ");
			}
			debug_printf( "(%d x %d)", n, a / n );
			++result;
			if( n*n == a ){
				break;
			}
			++result;
			b = a / (n+1);
		}
	}while( ++n <= b );
	debug_printf( "... " );
	return	result;
}

int	main(){
	for( int	n = 0; n < 60; ++n ){
		int	cdivisors = divisors_count( n+1 );
		debug_printf( "... %d の約数の数は %d個\n", n+1, cdivisors );
	}
	return	0;
}

再帰

ループは再帰にできる

int	divisors_count( int	a ){
	struct detail {
		static int	callback( int	a, int	n, int	b ){
			int	result = 0;
			if( n <= b ){
				if( !( a % n )){
					if( n > 1 ){
						debug_printf( ", " );
					}
					debug_printf( "(%d x %d)"), n, a / n );
					++result;
					if( n*n != a ){
						++result;
					}
					result += callback( a, n+1, a / (n+1));
				}
				else{
					result = callback( a, n+1, b );
				}
			}
			return	result;
		}
	};
	return	detail::callback( a, 1, a );
}

int	main(){
	for( int	n = 0; n < 60; ++n ){
		int	cdivisors = divisors_count( n+1 );
		debug_printf( "... %d の約数の数は %d個\n", n+1, cdivisors );
	}
	return	0;
}

テンプレート

再帰条件をコンパイル時に決定できる再帰はテンプレートにできる

template<int lhs,int rhs> struct less_than_or_equal_to_t {
	static const bool	value = ( lhs <= rhs );
};
template<int max_value,int n> struct is_divisor_of_t {
	static const bool	value = !( max_value % n );
};
template<int max_value,int n> struct is_sqrt_of_t {
	static const bool	value = ( n*n == max_value );
};
template<int N, int n = 1, int	max_value = N, int cdivisors = 0, bool = is_divisor_of_t<N,n>::value, bool = less_than_or_equal_to_t<n,max_value>::value> struct divisors_count_helper_t {
	static const int	value = divisors_count_helper_t<N,n+1,max_value,cdivisors>::value;
};
template<int N,int n,int cdivisors,bool = is_sqrt_of_t<N,n>::value> struct divisors_count_increment_helper_t {
	static const int	next = cdivisors+2;
};
template<int N,int n,int cdivisors> struct divisors_count_increment_helper_t<N,n,cdivisors,true> {
	static const int	next = cdivisors+1;
};
template<int N, int n, int	max_value, int cdivisors> struct divisors_count_helper_t<N,n,max_value,cdivisors,true,true> {
	static const int	value = divisors_count_helper_t<N,n+1,N/(n+1),divisors_count_increment_helper_t<N,n,cdivisors>::next>::value;
};
template<int N, int n, int	max_value, int cdivisors, bool is_divisor> struct divisors_count_helper_t<N,n,max_value,cdivisors,is_divisor,false> {
	static const int	value = cdivisors;
};
template<int n> struct divisors_count_t {
	static const int	value = divisors_count_helper_t<n>::value;
};

template<int	max_value,int n=1, bool = less_than_or_equal_to_t<n,max_value>::value> struct divisors_count_print_helper_t {
	static void	print(){
	}
};
template<int	max_value,int n> struct divisors_count_print_helper_t<max_value,n,true> {
	static void	print(){
		debug_printf( "%d の約数の数は %d個\n", n, divisors_count_t<n>::value );
		divisors_count_print_helper_t<max_value,n+1>::print();
	}
};

int	main(){
	divisors_count_print_helper_t<60>::print();
	return	0;
}

テンプレートその２

約数の数を数えるだけだと何が約数かわからないので、約数も print してみる

template<int lhs,int rhs> struct less_than_or_equal_to_t {
	static const bool	value = ( lhs <= rhs );
};
template<int max_value,int n> struct is_divisor_of_t {
	static const bool	value = !( max_value % n );
};
template<int max_value,int n> struct is_sqrt_of_t {
	static const bool	value = ( n*n == max_value );
};
template<int N,int n,int cdivisors,bool = is_sqrt_of_t<N,n>::value> struct divisors_count_increment_helper_t {
	static const int	next = cdivisors+2;
};
template<int N,int n,int cdivisors> struct divisors_count_increment_helper_t<N,n,cdivisors,true> {
	static const int	next = cdivisors+1;
};
template<int N,int n,int> struct print_divisor_helper_t {
	static void	print(){
		debug_printf( ", (%d x %d)", n, N / n );
	}
};
template<int N,int n> struct print_divisor_helper_t<N,n,0> {
	static void	print(){
		debug_printf( _T("(%d x %d)", n, N / n );
	}
};
template<int N, int n = 1, int	max_value = N, int cdivisors = 0, bool = is_divisor_of_t<N,n>::value, bool = less_than_or_equal_to_t<n,max_value>::value> struct divisors_count_helper_t {
	static const int	value = divisors_count_helper_t<N,n+1,max_value,cdivisors>::value;
	static void	print(){
		divisors_count_helper_t<N,n+1,max_value,cdivisors>::print();
	}
};
template<int N, int n, int	max_value, int cdivisors> struct divisors_count_helper_t<N,n,max_value,cdivisors,true,true> {
	static const int	value = divisors_count_helper_t<N,n+1,N/(n+1),divisors_count_increment_helper_t<N,n,cdivisors>::next>::value;
	static void	print(){
		print_divisor_helper_t<N,n,cdivisors>::print();
		divisors_count_helper_t<N,n+1,N/(n+1),divisors_count_increment_helper_t<N,n,cdivisors>::next>::print();
	}
};
template<int N, int n, int	max_value, int cdivisors, bool is_divisor> struct divisors_count_helper_t<N,n,max_value,cdivisors,is_divisor,false> {
	static const int	value = cdivisors;
	static void	print(){
	}
};
template<int n> struct divisors_count_t {
	static const int	value = divisors_count_helper_t<n>::value;
	static void	print(){
		debug_printf( "%d の約数は ", n );
		divisors_count_helper_t<n>::print();
		debug_printf( " の %d個\n", value );
	}
};

template<int	max_value,int n=1, bool = less_than_or_equal_to_t<n,max_value>::value> struct divisors_count_print_helper_t {
	static void	print(){
	}
};
template<int	max_value,int n> struct divisors_count_print_helper_t<max_value,n,true> {
	static void	print(){
		divisors_count_t<n>::print();
		divisors_count_print_helper_t<max_value,n+1>::print();
	}
};

int	main(){
	divisors_count_print_helper_t<60>::print();
	return	0;
}

テンプレートその３

約数のペアじゃなくて 1 から順番に print してみると

template<int lhs,int rhs> struct less_than_t {
	static const bool	value = ( lhs < rhs );
};
template<int lhs,int rhs> struct less_than_or_equal_to_t {
	static const bool	value = ( lhs <= rhs );
};
template<int max_value,int n> struct is_divisor_of_t {
	static const bool	value = !( max_value % n );
};
template<int max_value, int n = 1, int cdivisors = 0, bool = is_divisor_of_t<max_value,n>::value, bool = less_than_or_equal_to_t<n*2,max_value>::value> struct divisors_count_helper_t {
	static const int	value = divisors_count_helper_t<max_value,n+1,cdivisors>::value;
	static void	print(){
		divisors_count_helper_t<max_value,n+1,cdivisors>::print();
	}
};
template<int max_value, int n, int cdivisors> struct divisors_count_helper_t<max_value,n,cdivisors,true,true> {
	static const int	value = divisors_count_helper_t<max_value,n+1,cdivisors+1>::value;
	static void	print(){
		debug_printf( ",%d", n );
		divisors_count_helper_t<max_value,n+1,cdivisors+1>::print();
	}
};
template<int max_value, int cdivisors> struct divisors_count_helper_t<max_value,1,cdivisors,true,true> {
	static const int	value = divisors_count_helper_t<max_value,1+1,cdivisors+1>::value;
	static void	print(){
		debug_printf( "1" );
		divisors_count_helper_t<max_value,1+1,cdivisors+1>::print();
	}
};
template<int max_value, int n, int cdivisors, bool is_divisor> struct divisors_count_helper_t<max_value,n,cdivisors,is_divisor,false> {
	static const int	value = cdivisors;
	static void	print(){
	}
};
template<int n> struct divisors_count_t {
	static const int	value = divisors_count_helper_t<n>::value;
	static void	print(){
		debug_printf( "%d の約数は ", n );
		divisors_count_helper_t<n>::print();
		debug_printf( " の %d個\n", value );
	}
};

int	main(){
	divisors_count_t<60>::print();
	return	0;
}