[C++] 백준 11653. 소인수분해

#include <iostream>

using namespace std;

void sort(int *num, int size);

int isPrime(int n);

int main() {

int a;

cin >> a;

int elem[50];

int index = 0;

int count = 2;

while (a != 1) {

if (isPrime(a) == 1) {

elem[index++] = a;

break;

}

else if (a % count == 0 && isPrime(count) == 1) {

a /= count;

elem[index++] = count;

count = 2;

}

else

count++;

}

sort(elem, index);

for (int i = 0; i < index; i++)

cout << elem[i] << endl;

}

int isPrime(int n)

{

int i = 0;

if (n == 2 || n == 3)

return 1;

int last = n / 2; //약수가 없는 수가 소수이므로 2부터 n/2(자기자신/2)까지만 확인하면 됨

for (i = 2; i <= last; i++)

{

if ((n % i) == 0)

return 0;

}

return 1;

}

void sort(int *num, int size)

{

int i = 0, j = 0;

int temp = 0;

for(j = 0; j < size; j++)

{

for(i = 0; i < size-1; i++)

{

if(num[i] >= num[i+1])

{

temp = num[i];

num[i] = num[i+1];

num[i+1] = temp;

}

}

}

}

소수를 구하는 함수를 구하고 소수이면서 나누어 떨어지는 수를 구하면 쉽게 풀 수 있다.