素因数の素朴な求め方
C++で力技で素因数分解するプログラム
使用する場合はfactors(100)とかすれば、
コンソールに素因数が出力される。
再帰を使っているので、因数が多すぎるとスタックオーバーフローするかも。
数値はuint64_tを使っているので64bitまでが適用範囲。
#include "stdafx.h" #include <iostream> #include <stdint.h> #include <vector> // create a vector includes prime factors std::vector<uint64_t> *findPrime(uint64_t num) { for (uint64_t i = 2; i < num; i++) { if ((num % i) == 0) { std::vector<uint64_t> *vc; vc = findPrime(num / i); vc->push_back(i); return vc; } } std::vector<uint64_t> *v = new std::vector<uint64_t>(); v->push_back(num); return v; } int factors(uint64_t num) { std::cout << "--- " << num << " ---" << std::endl; std::vector<uint64_t> *v = findPrime(num); std::vector<uint64_t>::iterator it = v->begin(); while (it != v->end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; return 0; }