素因数分解を行うプログラム サンプルコード JS/PHP

JavaScript
スポンサーリンク




スポンサーリンク

概要

ある任意の正の整数の素因数を配列で返すサンプルコードを紹介します。

サンプルコード

JavaScript

パターン1 : 純粋な素因数分解

function pf(n) {
    var result = [];

    if (n === 1) {
        return [1];
    }

    var init = 2;

    while ( n !== 1 ) {
        var i = init;
        while (i < Number.MAX_SAFE_INTEGER) {
            if (n % i == 0) {
                result.push(i)
                n /= i;
                break;
            }
            i++;
        }
        init = i;
    }
    return result;
}

デバッグ

console.log(JSON.stringify(pf(1)))
console.log(JSON.stringify(pf(4)))
console.log(JSON.stringify(pf(27)))
console.log(JSON.stringify(pf(972439611840)))
// [1]
// [2,2]
// [3,3,3]
// [2,2,2,2,2,2,3,3,3,5,103,103,103,103]

パターン2 : 指数部と仮数部に分ける

function pf(n) {
    var result = {};
    
    if (n === 1) {
        return {"1":1}
    }

    var init = 2;

    while (n !== 1) {
        var i = init;
        while (i < Number.MAX_SAFE_INTEGER) {
            if (n % i === 0) {
                n /= i;
                if (!(result[i] > 0)) {
                    result[i] = 0;
                }
                result[i]++;
                break;
            }
            i++;
        }
        init = i;
    }
    return result;
}

デバッグ

console.log(JSON.stringify(pf(1)))
console.log(JSON.stringify(pf(4)))
console.log(JSON.stringify(pf(27)))
console.log(JSON.stringify(pf(972439611840)))
// {"1":1}
// {"2":2}
// {"3":3}
// {"2":6,"3":3,"5":1,"103":4}

PHP

function pf($n) {
    $result = array();

    if ($n === 1) {
        return [1];
    }

    $init = 2;

    while ( $n !== 1 ) {
        $i = $init;
        while ($i < 0xFFFFFF) {
            if ($n % $i == 0) {
                $result[] = $i;
                $n /= $i;
                break;
            }
            $i++;
        }
        $init = $i;
    }
    return $result;
}
JavaScriptPHPアルゴリズム
スポンサーリンク
スポンサーリンク
スポンサーリンク
404 Motivation Not Found