#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, tmp, i, max, j;
vector<int> nums;
vector<bool> vec;
vector<int> primenumbers;
//input
cin >> n;
for (i = 0; i < n; i++) {
cin >> tmp;
nums.push_back(tmp);
}
//find primenumbers
max = *max_element(nums.begin(), nums.end());
for (i = 2; i <= max; i++) {
vec.push_back(true);
}
for (i = 2; i <= max; i++) {
if (vec[i]) {
for (j = i+i; j <= max; j += i) {
vec[j] = false;
}
}
}
for (i = 2; i <= max; i++) {
if (vec[i]) {
primenumbers.push_back(i);
}
}
//output
for (i = 0; i < n; i++) {
j = 0;
while(nums[i] >= primenumbers[j] * primenumbers[j]) {
if (nums[i] % primenumbers[j] == 0) {
cout << primenumbers[j] << " ";
nums[i] /= primenumbers[j];
}
else j++;
}
cout << nums[i] << "\n";
}
return 0;
}
소인수 찾는 로직 - primefactor()
방법1 :
2부터 n까지 반복문을 돌면서 primefactors
를 완성하는 로직
input이 매우 크기 때문에 시간초과남
방법2 :
재귀로 풀어야 겠다 -> 소수를 만나면 재귀 호출 -> 소수를 찾는 로직 필요
입력 받은 Ki
값들 중 최대값을 기준으로 eratos()
를 호출
소수들을 구할 수 있으며 이는 primenumbers
에 모두 들어가 있음
primenumbers
를 돌면서 소수를 만나면 재귀호출
방법2.1 :
시간 초과를 줄이는 방법 찾기
vector<int>
를 출력하는 pprint()
사용하지 않고 바로바로 출력하기
primenumbers[i]
가 여러번 출력되는 경우도 존재하므로 if else 문
으로 나누어서 else 일 때만 index 1씩 증감
방법2.2 :
함수 없애고 main()
에 다 넣기
방법 2.3 :
출력할 때 while 문
반복횟수 줄이기
숫자 < 소수*소수
인 경우 그냥 출력하면 됨 -> 남은 것 or 숫자가 소수
for (i = 0; i < n; i++) {
j = 0;
while(nums[i] >= primenumbers[j] * primenumbers[j]) {
if (nums[i] % primenumbers[j] == 0) {
cout << primenumbers[j] << " ";
nums[i] /= primenumbers[j];
}
else j++;
}
cout << nums[i] << "\n";
}
소인수찾는 로직 - primefactor()
main()
에서 primefactor()
실행 -> 나눠지는 수가 소인수임
소인수를 찾으려면 소수를 찾아야 함
방법1 : 소수를 찾는 로직 -> 소인수 찾는 로직 -> main 로직
: 시간이 오래 걸릴 것 같음
방법2 : 제곱근 수를 재귀적으로 찾아서 나누어보고 없으면 1과 자기자신을 출력
primefactor()
에서 vector<int>primefactors
를 찾고 리턴
primefactors
의 default 는 {1} 로 설정primefactors
에 n
을 push_back
하고 리턴하다가 약수를 모두 구하는 코드를 짜버림
#include <bits/stdc++.h>
using namespace std;
void pprint(vector<int> arr) {
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << "\n";
}
//약수 찾기
vector<int> primefactor(int n) {
vector<int> primefactors;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
primefactors.push_back(i);
primefactors.push_back(n/i);
}
}
sort(primefactors.begin(), primefactors.end());
primefactors.erase(unique(primefactors.begin(), primefactors.end()), primefactors.end());
return primefactors;
}
int main() {
int n, tmp;
vector<int> nums;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
nums.push_back(tmp);
}
for (int i = 0; i < n; i++) {
pprint(primefactor(nums[i]));
}
return 0;
}
sort
: 정렬을 함unique
: 연속된 중복 원소를 vector.end() 로 보냄erase
: 중복된 원소들이 모여있는 뒷부분을 삭제함sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());