LoginSignup
1
2

More than 3 years have passed since last update.

素因数分解

Last updated at Posted at 2019-12-01

ある整数num(num>=1)を素因数分解する方法

Python3.6.8

#Python3
import math

def calc(num):
    L =[1]
    for i in range(2, int(math.sqrt(num))+1): #iが素因数であるか、2から√numまで調べる
        while num % i==0:
            L.append(i)
            num = num//i
    if num !=1:
        L.append(num) #最後に残ったnumをリストに追加
    print(L)


calc(100)
[1, 2, 2, 5, 5]



C17++

//C17++
#include <bits/stdc++.h>
using namespace std;

void calc(int num){
    vector<int>L(1, 1); //L(要素数,初期値)
    int n = sqrt(num);

    for(int i=2; i<=n; i++){
        while (num % i==0){
            L.push_back(i);
            num = num/i;
        }
    }
    if(num !=1){
        L.push_back(num);
    }
    for(auto c:L){
        cout << c << ' ';
    }
}

int main(void){
    calc(90);

}
1 2 3 3 5

ありがとうございました。

参考文献
試し割り法 - Wikipedia
https://ja.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2