Problem 211

Project Euler

211 Divisor Square Sum
Problem 211 - Project Euler
約数関係の問題は、たいてい、因数分解・除算などは効率が良くないので、使えることが少ない。
では、どうするか？
ふるい。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 64000000LL
int main(){
  long long u, c, i, j, *s;
  u = (long long) sqrt(N);
  c = 0;
  s = malloc((N+1)*sizeof(long long));
  for(i=1;i<=u;i++){
    s[i*i] += i*i;
    for(j=i+1;j<=N/i;j++) s[j*i] += i*i + j*j;
  }
  for(i=1;i<=N;i++){
    j = floor(sqrt(s[i]));
    c += j*j==s[i] ? i: 0;
  }
  printf("%lld\n",c);
}

まぁ、Haskellで書いてもいいけどメンドウ、どうせ、Cのほうが速いし、短い。