159. 소인수분해

백준

1. Python

간단한 풀이

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

에라토스테네스의 체

n = int(input())

a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1): #지워 지지 않은 수 중 가장 작은 수 소수로
  if a[i]: 
    primes.append(i)
    for j in range(2*i, n+1, i): #2, 3, ...의 배수 모두 지우기
        a[j] = False
        
#primes.sort()
    
if n in primes: 
	print(n) 
else: 
  #answers = [] 

  for p in primes:
    if n % p == 0: 
      while(n % p == 0):   
        print(p)
        n = n // p


#for a in answers:
#	print(a)

2. C++

#include <cstdio>
#include <vector>
using namespace std;

bool che[3200];
vector<int> prime;
int n;

int main() {
    for (int i = 2 ; i < 3200 ; i++) {
        if (che[i]) continue;
        for (int j = i + i ; j < 3200 ; j += i) {
            che[j] = true;
        }
    }
    for (int i = 2 ; i < 3200 ; i++) {
        if (!che[i]) {
            prime.push_back(i);
        }
    }
    scanf("%d", &n);
    if (n == 1) {
        return 0;
    }
    for (int i = 0 ; i < prime.size() ; i++) {
        while (n % prime[i] == 0) {
            printf("%d\n", prime[i]);
            n /= prime[i];
        }
    }
    if (n > 1) {
        printf("%d\n", n);
    }
}