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

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

2018-12-249 min read

目次

  1. 概要
  2. サンプルコード

概要

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

サンプルコード

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;
}
Tags
javascript(109)
linux(54)
node.js(53)
amazon%20aws(47)
typescript(44)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
html5(29)
php(24)
centos(24)
python(22)
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0(21)
mac(21)
mysql(20)
canvas(19)
opencv(17)
%E9%9B%91%E8%AB%87(16)
docker(16)
wordpress(15)
atcoder(14)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
amazon%20s3(12)
red%20hat(12)
prisma(12)
ubuntu(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
mariadb(10)
react(9)
aws%20cdk(9)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
nestjs(8)
amazon%20lightsail(7)
next.js(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
iam(5)
amazon%20ec2(5)
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93(5)
aws%20amplify(5)
curl(4)
Author
githubzennqiita
ただの備忘録です。

※外部送信に関する公表事項