BOJ 11653번 :: 소인수분해

#문제

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

#작성 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int prime[10000000];
int numprime=0;
int INF = 10000000;
int main(){
    cin>>n;
    int tmp = n;
    
    for(int i=2; i<=n; i++){
        prime[i] = i;
    }
    for(int i=2, j; i*i<=n; i++){
        if( prime[i]==i ){
            numprime++;
            for(int j=i+i; j<=n; j=j+i){
                prime[j]=INF;
            }
        }
    }
    sort(prime, prime+numprime);
 
    int i=2;
    while(tmp!=1){
        while(tmp%prime[i]==0){
            tmp/=prime[i];
            cout<<prime[i]<<'\n';
        }
        i++;
    }
    return 0;
}

#include <iostream>
using namespace std;
 
int n;
int main(){
    cin>>n;
    int tmp = n;
    
    for(int i=2; i<=n; i++){
        while(tmp%i==0){
            tmp/=i;
            cout<<i<<'\n';
        }
    }
    return 0;
}

##

첫 코드는 에라토스테네스의 체를 이용한 코드이다. 200ms정도의 수행시간을 보였다.

두 번째 코드는 2부터 n까지 단순히 나누어떨어지지않을때까지 나눠서 n을 1로 만드는 방식이다. 약 32ms의 수행시간을 보였다.