FC2ブログ

# 約数の個数と和 Divisor
# 引数 自然数 ($X)
# 戻り値 約数の個数と和 (@Divisor)
sub DIVISOR{
my ($X) = @_;
my @Divisor = ();
my @PrimeFactorization = ();
my $Value = 0;
my $Power = 1;
my $Sum = 1;
my $Count = 1;
my $CountPrimeFactorization = 0;

# 自然数の確認
if($X < 2){
return 0;
}

# 素因数分解
# ポラード・ロー素因数分解法 Pollard's Rho Algorithm
@PrimeFactorization = POLLARDSRHOALGORITHM(int($X));
@PrimeFactorization = sort { $a <=> $b } @PrimeFactorization;
$CountPrimeFactorization = @PrimeFactorization - 1;
# 初期値
$Value = $PrimeFactorization[0];

for(my $i = 1; $i <= $CountPrimeFactorization; $i++){
if($Value != $PrimeFactorization[$i]){
# 約数の個数
$Count *= ($Power + 1);
# 約数の和
$Sum *= ((($Value ** ($Power + 1)) - 1) / ($Value - 1));

# 初期化
$Value = $PrimeFactorization[$i];
$Power = 1;
}else {
# 累乗
$Power++;
}
}

# 約数の個数 残り
$Count *= ($Power + 1);
# 約数の和 残り
$Sum *= ((($Value ** ($Power + 1)) - 1) / ($Value - 1));

# 約数の個数と和 Divisor
# [0] = 約数の個数 [1] = 約数の和
$Divisor[0] = $Count;
$Divisor[1] = $Sum;

return @Divisor;
}

# ポラード・ロー素因数分解法 Pollard's Rho Algorithm
# 引数 自然数 ($NaturalNumber)
# 戻り値 ポラード・ロー素因数分解法 (@PrimeFactorization)
sub POLLARDSRHOALGORITHM{
my ($NaturalNumber) = @_;
my @PrimeFactorization = ();
my $PMinus1Method = 0;
my $Position = 0;

# 自然数の確認
if($NaturalNumber < 1){
return 0;
}

$NaturalNumber = int($NaturalNumber);

while(($NaturalNumber > 1) && ($PMinus1Method != 1)){
# P-1法 P-1 Method
$PMinus1Method = &PMINUS1METHOD($NaturalNumber);

if($PMinus1Method != 1){
$NaturalNumber = $NaturalNumber / $PMinus1Method;

# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $PMinus1Method;
# 配列の位置
$Position++;
}else {
# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $NaturalNumber;
}
}

return @PrimeFactorization;
}

# P-1法 P-1 Method
# 引数 自然数 ($NaturalNumber);
# 戻り値 P-1法 ($PMinus1Method)
sub PMINUS1METHOD{
my ($NaturalNumber) = @_;
my $PMinus1Method = 0;
my @PrimeNumber = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);
my $A = 2;
my $M = 1;
my $X = 0;
my $GCD = 0;
my $Limit = 10000;

# 小さな素数を取り除く
for(my $i = 0; $i < @PrimeNumber; $i++){
$GCD = &EUCLIDEANALGORITHM($PrimeNumber[$i], $NaturalNumber);

if(1 != $GCD){
# P-1法 P-1 Method
$PMinus1Method = $GCD;

return $PMinus1Method;
}
}

# 計算
for(my $i = 2; $i < $Limit; $i++){
$M = $i;
# 値
$X = ($A ** $M) % $NaturalNumber;
next if($X == 1);
# 最大公約数
$GCD = &EUCLIDEANALGORITHM(($X - 1), $NaturalNumber);

# 素因数があるなら
last if(1 != $GCD);
}

# P-1法 P-1 Method
$PMinus1Method = $GCD;

return $PMinus1Method;
}

# ユークリッドの互除法 Euclidean Algorithm
# 引数 自然数 自然数 ($a, $b)
# 戻り値 最大公約数 ($EuclideanAlgorithm)
sub EUCLIDEANALGORITHM{
my ($a, $b) = @_;
my $EuclideanAlgorithm = 0;
my $A = int(abs($a));
my $B = int(abs($b));
my $Remainder = 1;

# 値の確認
if(($A == 0) || ($B == 0)){
return 0;
}

($A, $B) = ($B, $A) if($A < $B);

# 計算
while($Remainder != 0){
# 余り
$Remainder = $A % $B;

$A = $B;
$B = $Remainder;
}

# ユークリッドの互除法 Euclidean Algorithm
$EuclideanAlgorithm = $A;

return $EuclideanAlgorithm;
}


総当り
http://blog-imgs-36.fc2.com/a/m/a/amamiyaprog/Divisor1.txt

参考URL
約数 - Wikipedia
約数の個数と和

一言
P-1法で使用する$Limitの値が小さいと素因数分解しきれていないことがある
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

Author:雨宮
Firefoxを使用しているので気づかなかったけど、IE6でソースコードを上手くコピーできない

5/3
携帯用ならIE6でもソースコードをコピーできる
携帯用

検索フォーム


あわせて読みたいブログパーツ
一寸先は闇 RSS

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。