2013.02.02 Saturday
プロジェクトオイラー問題12
素因数分解して、素因数の数から約数の数を計算することにした。
そのためにはまず素因数分解関数を作る必要がある。
再帰を使って作った。
関数f(int n)は引数nをn = a×bのように因数分解する。
関数fの中で再帰的にf(a)、f(b)を呼べば芋づる式に因数分解できる。
素因数分解出来たら、次はそこから約数の数を計算する必要がある。
例えば
各グループから任意の数だけ抽出して積をとる。これが約数になる。
グループ1からは0個及び1個取り出す2パターン、
グループ2からは0または1または2の3パターンである。
ただし、全てのグループから0個取り出すと積が0になるのでそのような場合を除く。
よって約数の数は
つまり
そのためにはまず素因数分解関数を作る必要がある。
再帰を使って作った。
関数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;
}
#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;
}
約数は1を数えない方針ですか?
posted by tom ,2013/02/02 8:59 AM
0になる場合を除いて1の場合を入れるので説明の-1は不要ですね。
コードの方は合ってると思いますが。
posted by jajagacchi ,2013/02/02 10:20 PM