[SCCC] 어려운 소인수분해_16563번

손시연·2022년 6월 10일
0

SCCC

목록 보기
10/18

어려운 소인수분해_16563번

코드

#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} 로 설정
    • escape : sqrt(n) 의 값이 1 과 같아지면 primefactorsnpush_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;
}

C++ 개념

  • vector 중복 원소 제거
    • sort : 정렬을 함
    • unique : 연속된 중복 원소를 vector.end() 로 보냄
    • erase : 중복된 원소들이 모여있는 뒷부분을 삭제함
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
profile
Server Engineer

0개의 댓글