[C/C++] 프로젝트 오일러 #72 분수 세기(수학)

이번 문제는 분수를 세는 문제입니다.

 

counting rational numbers

 

해당 문제는 아래 링크입니다.

https://projecteuler.net/problem=72

Problem 72 - Project Euler

 

이 문제는 분모의 범위가 정해졌을 때, 기약분수로 표현할 수 있는 분수는 총 몇개인가에 대한 문제입니다.

모든 경우를 다 따져서 기약분수로 만들어서 겹치는 것 제외하면 되겠다고 생각할 수 있지만, 이것이 생각처럼 쉽지 않습니다.

 

\(d \leq 8\)인 분모 d를 갖는 기약분수는 다음과 같습니다.

1/8 3/8 5/8 7/8 1/7 2/7 3/7 4/7 5/7 6/7 1/6 5/6 1/5 2/5 3/5 4/5 1/4 3/4 1/3 2/3 1/2 으로 총 21개의 기약분수가 있습니다.  순서는 중요하지 않아서 분모가 큰 것부터 작은 순으로 배열했습니다.

 

이것을 일일이 한다면, d 의 범위가 문제에서처럼 1,000,000이라면, 실제 검사해야 하는 분수의 갯수는 499,999,500,000 개가 있습니다.  단순 계산만 해도 꽤 시간이 걸립니다.

 

전 정수론을 이용했습니다.  범위안의 모든 수의 오일러 수를 구한 후, 그 합을 계산했습니다.

즉, 다음의 같이 했죠.

 

\[ H(n) = \sum_{k=2}^{n} \varphi(k) \]

 

가 제가 구한 풀이방법입니다.  물론 오일러의 수를 구하기 위해서는 미리 소수를 필요한만큼 구합니다.  1,000,000을 소인수분해하기 위해서는 1,000 이하의 소수만 구하면 됩니다.  제 경우에는 답을 구하는데 524ms가 걸렸습니다.  꽤 시간이 많이 걸리네요.

 

아래에 제가 짠 소스를 첨부합니다.  소스는 참고용으로만 봐주세요.

 

더 좋은 솔루션이 있으면 댓글 남겨주시면 고맙겠습니다.

 

//----------------------------------------------------------------------------------------
//  Project Euler #72 - Counting fractions
//    - by Aubrey Choi
//    - created at 2015-10-05
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>

int primes[10000];
int pcount = 0;

int phi(int n)
{
  int v = 1;
  for( int i = 0 ; n > 1 && i < pcount ; i++ )
  {
    if( n%primes[i] == 0 )
    {
      v *= primes[i]-1;
      n /= primes[i];
      while( n%primes[i] == 0 ) { v *= primes[i]; n /= primes[i]; }
    }
  }
  if( n > 1 ) v *= (n-1);
  return v;
}

void solve1()
{
  primes[pcount++] = 2;
  primes[pcount++] = 3;
  primes[pcount++] = 5;
  primes[pcount++] = 7;
  for( int p = 11 ; p < 1000 ; p += 2 )
  {
    bool isPrime = true;
    for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
    {
      if( p%primes[i] == 0 ) { isPrime = false; break; }
    }
    if( isPrime ) primes[pcount++] = p;
  }

  long long sum = 0;
  for( int n = 2 ; n <= 1000000 ; n++ )
  {
    sum += phi(n);
  }
  printf("Ans = %lld\n", sum);
}

int main()
{
  clock_t t;

  t = clock();

  solve1();

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