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 = ;
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: ;
}
printf("%lldn",c);
}

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