[백준알고리즘]11653번 소인수분해 python,c++

문제: 

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력:

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다.

소인수분해:

http://study.zum.com/book/11455

소인수분해는 다들 알고 있듯이, 나눠지지 않는 수로 이루어진 식으로 나타난다고 쉽게 생각하면 된다.

 

예제:

소수로 이루어진 수들로 출력을 해야 하므로,

while문으로 계속 돌면서

if문을 통해 나눠지면 print, 나눠지지 않으면 계속 돌리면 될 듯 하다.

 

Python

간단하게 num을 입력받고, 소수 2부터 나눠보면 된다.

계속 돌면서 나눠지면 print하고, 아니면 +1을 해준다.

num = int(input()); 
i=2
while num!=1 :
    if num%i == 0:
        num = num/i
        print(i)
    else : i+=1

 

C++

#include <iostream>
using namespace std;

int main(){
    int num;
    int i = 2;
    cin >> num;

    while(num != 1){
        if(num % i == 0){
            num = num/i;
            cout << i << "\n";
        }
        else
            i++;
    }
}

 

Python이 확실히 시간이 더 걸린다.