2以上の整数nについて、その素因数の和sf(n)の計算法を考える。

例えば、2 = 2 なので、sf(2) = 2。
6 = 2*3 なので、sf(6) = 2+3 = 5。
8 = 2*2*2 なので、sf(8) = 2+2+2 = 6。

2から30までの整数についての sf(n)の値は以下の通り。
2,3,4,5,5,7,6,6,7,11,7,13,9,8,8,17,8,19,9,10,13,23,9,10,15,9,11,29,10.

#include <stdio.h>
#include <string.h>
#define MAX 500000
#define ROOT_MAX 707
int sf[MAX+1];
void sieve(void)
{
    register int i, j, k;
    /* memset(sf, 0, sizeof(sf)); */
    for (j = 2; j <= MAX; j <<= 1) {
        for (i = j; i <= MAX; i += j) sf[i] += 2;
    }
    for (k = 3; k <= MAX; k += 2) {
        if (sf[k] == 0) {
            for (j = k; j <= MAX; j *= k) {
                for (i = j; i <= MAX; i += j) sf[i] += k;
                if (k > ROOT_MAX) break;
            }
        }
    }
}

計算できる最大値 MAX は適宜変えること。ROOT_MAXはMAXの平方根。関数の実行が終了した時点で、配列sf に2以上、MAXまでの素因数の和が格納される。

Comments are closed.

Post Navigation