프로젝트 오일러 #63 제곱수의 자릿수 세기

제곱수 문제이긴 하지만, 의외로 이 문제는 쉽습니다.  난이도도 5%입니다.  문제는 n자리의 수중에 어떤 수의 n제곱이 되는 수가 몇개나 존재할까입니다.  예를 들어서 \(16807=7^5\) 인데, 16807은 5자리의 수이고 7의 5제곱이 되는 수죠.

 

이 문제의 링크는 아래에 있습니다.

https://projecteuler.net/problem=63

Problem 63 - Project Euler

 

그냥 단순 무식하게 풀어도 이 문제는 큰 하자가 없습니다.  일단, 제곱을 할 수는 10 미만의 수입니다.  10의 n제곱수는 자릿수로는 n+1자리가 되기 때문이죠.  당연히 10보다 큰 수는 말할 것도 없겠죠.  문제만 보면 어려워보이지만, 이렇게 문제에 숨겨져있는 숫자의 한계를 알게 되면 문제가 쉬워지게 됩니다.

 

그러니 1에서 9까지 제곱해가면서 자릿수 계산하시면 됩니다.  오버플로우만 조심하면 별 문제 없을겁니다.  예를 들어서 3의 3제곱은 27이 되겠죠.  27은 두자리 숫자니까 그 다음에 더 3을 곱해도 자릿수가 제곱한 횟수보다 커지지 않습니다.  이렇게 단순하게 계산해도 전혀 문제가 없는 프로그램입니다.

 

2를 제곱해서, 과연 얼마나 많은 같은 제곱자리수를 얻을 수 있을까요.  간단하게, 2의 1제곱하면 2이니까, 하나는 만족합니다.  2의 2제곱은 4이니까, 그 후는 볼 것이 없겠죠.  그래서 2로 만들 수 있는 최대 갯수는 1입니다.  저는 이것을 식으로 다음과 같이 표현했습니다.

 

 

n이 1이라면 저 값은 1이 되겠죠. n이 2라면 약 1.43으로 역시 1이 됩니다.  n이 3이라면 1.912 정도로 역시 1입니다.  3의 제곱하면 9이니까, 거의 10에 가깝죠.  n이 4라면, 2.51정도로 2가 되는 것을 알 수 있습니다.  4의 제곱은 16으로, 처음으로 제곱수가 두자릿수가 됩니다.  이렇게 계산을 하면 손으로도 얼마든지 계산을 할 수가 있습니다.

 

제가 작성한 코드는 다음과 같습니다.

 

 

//----------------------------------------------------------------------------------------
//  Project Euler #63 - Powerful digit counts
//    - by Aubrey Choi
//    - created at 2015-10-01
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>
#include <math.h>

void solve1()
{
  int count = 1;
  for( int i = 2 ; i < 10 ; i++ )
  {
    count += 1.0/(1.0-log10((double)i));
  }
  printf("Ans = %d\n", count);
}

int main()
{
  clock_t t;

  t = clock();

  solve1();

  printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}