[c++] 백준 11653 - 소인수분해(수학)

0. [c++] 백준  -

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

1. 풀이

입력받는 정수(N)의 크기가 10,000,000이여서 O(N)의 구현을 해보았다.

밑의 함수에서 i가 소수인지 고려를 하지 않고 진행하는 것을 볼 수 있다.

이렇게 한 이유는 소수의 배수인 경우 이미 앞에서 전처리가 끝난 상황이기 때문에 while문으로 넘어가는 경우가 발생하지 않아 이렇게 구현을 해보았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include<iostream> #include<algorithm> #include<vector>   using namespace std;   typedef unsigned long long ull;   int arr[51]; int prime[101];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;       if (N == 1)         return 0;     else {         for (int i = 2; i <= N; i++) {             while (N % i == 0) {                 cout << i << "\n";                 N /= i;             }         }     }       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!