634をちょっと改造
#include <stdio.h>
#include <stdlib.h>

#define N 100

int main(void) {
int i, j, k, a[N + 1] = {0}, max, *cnt, sum = 0;

for(max = 0, i = N; i; i >>= 1) max++;

cnt = calloc(max, sizeof(int));
cnt[0] = N - 1;

for(i = 2; i < max; i++) {
for(j = (i & 1) ? N / i + 1 : N / 2 + 1; j <= N; j++) {
for(k = 2; k < i; k++) {
if(i * j > k * N) continue;
if(i * j % k == 0) break; }
if(k == i) cnt[i]++; } }

for(i = 2; i * i <= N; i++) for(j = i * i, k = 2; j <= N; j *= i, k++) if(a[j] == 0) a[j] = k;
for(i = 2; i <= N; i++) sum += cnt[a[i]];

printf("%d\n", sum);

free(cnt);

return 0;}