<< プロジェクトオイラー問題11 | top | プロジェクトオイラー問題13 >>

プロジェクトオイラー問題12

 500個以上の約数をもつ最初の三角数を求める問題。
愚直に約数を数えていては計算に時間がかかりすぎる。
結構苦戦した。
解説は続きから。
素因数分解して、素因数の数から約数の数を計算することにした。
そのためにはまず素因数分解関数を作る必要がある。
再帰を使って作った。
関数f(int n)は引数nをn = a×bのように因数分解する。
関数fの中で再帰的にf(a)、f(b)を呼べば芋づる式に因数分解できる。
素因数分解出来たら、次はそこから約数の数を計算する必要がある。
例えば
28 = 7×2×2
の場合を考える。グループ1には7がひとつ、グループ2には2がふたつあると考える。
各グループから任意の数だけ抽出して積をとる。これが約数になる。
グループ1からは0個及び1個取り出す2パターン、
グループ2からは0または1または2の3パターンである。
ただし、全てのグループから0個取り出すと積が0になるのでそのような場合を除く。
よって約数の数は
2×3-1
となる。
つまり
約数の数=(グループ1の個数+1)×(グループ2の個数+1)×…-1
である。(2/2追記 1が約数に入っていないので+1する。よって最後の-1は不要)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int N;//素因数の数
int data[1024];//素因数配列

void factorization(int n)//因数分解関数。Nとdataの初期化を忘れないこと! dataには降順で素因数が入る。
{
    for(int i=2;i<=n/2;i++)
    {
        if(n%i==0)
        {
            factorization(n/i);
            factorization(i);
            return;
        }
    }
//    printf("%d¥n",n);
    data[N] = n;
    N++;
}

int main()
{
    time_t start,stop;
    start = clock();
    int i,j;
    int sum = 0;
    int NoOfDiv = 1;
   
    int n = 1;
    while(NoOfDiv<500)
    {
        sum += n++;
       
        N = 0;
        j = 0;
        NoOfDiv = 1;
        for(i=0;i<1024;i++)
        {
            data[i] = 0;
        }
        factorization(sum);
        for(i=0;i<N;i++)
        {
            if(data[i]!=data[i+1])
            {
                NoOfDiv *= i-j+2;
                j = i+1;
            }

        }
    }
    printf("sum=%d¥n",sum);
   
    stop = clock();
    printf("%f[sec]¥n",(stop-start)/1000.);
   
    return 0;
}
ジャジャガッチ | 数学 | 01:11 | comments(2) | trackbacks(0) |

スポンサーサイト

スポンサードリンク | - | 01:11 | - | - |
Comment
僕もやっとできました。
約数は1を数えない方針ですか?

posted by tom ,2013/02/02 8:59 AM

あ、1は約数に入れているので説明の方が間違ってますね。
0になる場合を除いて1の場合を入れるので説明の-1は不要ですね。
コードの方は合ってると思いますが。

posted by jajagacchi ,2013/02/02 10:20 PM










Trackback
URL:

03
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH