12. Highly divisible triangular number

1. 개요

문제는 이곳에서 확인할 수 있다. 먼저 \(n\)번째 triangular number는 1부터 정수 \(n\)까지의 합으로 정의된다. 예를 들어 3번째 triangular number는 \(1+2+3=6\)이다. 문제의 목표는, 처음으로 500개가 넘는 제수(divisor)를 가지는 triangular number를 찾는 것이다. 문제를 풀고나니 더 좋은 방법이 있었기 때문에 이를 비교하기 위하여 각 풀이마다 시간을 잰다.

2. Ver 1.0

가장 간단한 방법은 어떤 triangular number를 그 숫자의 제곱근보다 작거나 같은 자연수로 나누어 가면서 제수의 수를 세는 것이다. 

using System;
using System.Diagnostics;

class ProjectEuler
{
	static void Main(string[] args)
	{
		Stopwatch sw = new Stopwatch();
		sw.Start();
		
		ulong triangle_number = 0;
		ulong i = 0;
		
		while(true)
		{
			i += 1;
			triangle_number += i;
			
			double sqrt_triangle_number = Math.Sqrt(triangle_number);
			int count = 0;
			ulong divisor = 0;
			
			// triangle_number의 제곱근보다 작거나 같은 자연수에 대해서만 세면 된다.
			for(divisor = 1; divisor <= sqrt_triangle_number; divisor++)
			{
				if(triangle_number % divisor == 0)
				{
					count++;
				}
			}
			count *= 2;
			
			// 제곱의 경우 하나를 덜센다.
			if(divisor == sqrt_triangle_number)
			{
				count -= 1;
			}
			if(count >= 500)
			{
				break;
			}
		}
		
		Console.WriteLine(triangle_number);
		sw.Stop();
		Console.WriteLine(sw.ElapsedMilliseconds.ToString() + "ms");
	}
}

답은 76576500이며 PC에서 약 500ms가 걸렸다.

3. Ver 2.0

문제를 풀고 사람들의 의견을 보니 더 좋은 방법이 있어 이를 소개한다. 

2 이상의 자연수 \(N\)은 \(N=p_{1}^{n_{1}} \times p_{2}^{n_{2}} \times...\times p_{k}^{n_{k}}\)와 같이 표현된다. 단, \(p_{k}\)는 소수이며 \(n_k\)는 그 소수에 대한 제곱수이다. 예를 들어, \(120=2^{3}\times3\times5\)와 같다. 또한 \(N\)의 제수의 개수 \(D(N)\)은 \((n_{1}+1)(n_{2}+1) ... (n_{k}+1)\)와 같다. 예를 들어 120의 제수의 개수는 \((3+1)(1+1)(1+1)=16\)이다. 

\(n\)번째 triangular number \(t_n\)은 \( t_n=n(n+1)/2 \)와 같고 \(n\)과 \(n+1\)은 서로소이다. 따라서 \(D(t_n)\)은 \(n\)이 짝수인 경우 \(D(t_n)=D(n/2)D(n+1)\), \(n\)이 홀수인 경우 \(D(t_n)=D(n)D((n+1)/2)\)이 된다. 

위의 방법을 사용하여 아래와 같은 코드를 작성한다. 중복 계산을 막기 위하여 \(D(N)\)을 저장하며 소수는 에라스토테네스의 체를 사용하여 찾는다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class ProjectEuler
{
	static List<int> prime_array;
	
	static void Main(string[] args)
	{
		Stopwatch sw = new Stopwatch();
		sw.Start();
		
		// 소수를 확보한다.
		make_prime_array();
		
		int cnt = 0;
		int n = 3;
		Dictionary<int, int> D_set = new Dictionary<int, int>();
		
		while (cnt < 500)
		{
			// 0번째, 1번째 원소는 각각 n, n+1
			List<int> temp_term = new List<int>();
			List<int> idx = new List<int>();
			
			if (n % 2 == 0)
			{
				idx.Add(n/2);
				idx.Add(n+1);
			}
			else
			{
				idx.Add(n);
				idx.Add((n+1)/2);
			}
			
			// 기존에 계산한 D(n)이 있다면 사용한다.
			foreach(int i in idx)
			{
				if(!D_set.ContainsKey(i))
				{
					D_set[i] = D(i);
				}
				temp_term.Add(D_set[i]);
			}
			cnt = temp_term.Aggregate(1,(k,j)=>k*j);
			n += 1;
		}
		
		Console.WriteLine(n*(n-1)/2);
		
		sw.Stop();
		Console.WriteLine(sw.ElapsedMilliseconds.ToString()+"ms");
		
	}
	
	///<summary>
	/// 자연수 n을 소인수분해 후 number of divisors를 구한다.
	///</summary>
	static int D(int n)
	{
		int i = 0;
		List<int> cnt = new List<int>();
		
		while (n>1)
		{
			if (n % prime_array[i] == 0)
			{
				cnt.Add(0);
				while (n % prime_array[i] == 0)
				{
					n /= prime_array[i];
					cnt[cnt.Count-1] += 1;
				}
			}
			
			i += 1;
			
			// 소수의 개수가 충분하지 않다면 더 확보한다.
			if( i >= prime_array.Count)
			{
				make_prime_array();
			}
		}
		return cnt.Aggregate(1,(k,j)=>k*(j+1));
	}
	
	///<summary>
	/// 에라토스테네스의 체를 이용하여 소수를 찾는다.
	///</summary>
	static void make_prime_array()
	{
		int prime_candidate = 0;
		int max_prime_candidate = 0;
		
		if(prime_array == null)
		{
			prime_array = new List<int>();
			prime_array.Add(2);
			prime_candidate = 3;
		}
		else
		{
			prime_candidate = prime_array[prime_array.Count-1] + 2;
		}
		max_prime_candidate = prime_candidate * 2;
		
		while(prime_candidate < max_prime_candidate)
		{
			prime_array.Add(prime_candidate);
			prime_candidate += 2;
		}
		
		for(int i = 3; i <= Math.Sqrt(max_prime_candidate); i+=2)
		{
			prime_array.RemoveAll(p=> p>i && p%i==0);
		}
	}
}

답은 Ver 1.0과 같이 76576500이지만 Ver 1.0과 동일한 수행 환경에서 실행 시간은 20ms가 걸리지 않았다.