정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.
https://pushback.tistory.com/8
1. 기본
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int num;
int divisor = 2;
cin >> num;
while (num != 1) {
// 나누어 떨어지지 않으면
if (num % divisor != 0) {
divisor++;
}
else {
cout << divisor << '\n';
num /= divisor;
}
}
return 0;
}
2. 개선 ver.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int num;
int divisor = 2;
cin >> num;
while (num != 1) {
if (num % divisor != 0) {
// divisor가 짝수면 + 1, 홀수면 + 2
divisor = divisor % 2 == 0 ? divisor + 1 : divisor + 2;
}
else {
cout << divisor << '\n';
num /= divisor;
}
}
return 0;
}
3. \(\sqrt n\)까지 보기
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll num;
ll divisor = 2;
cin >> num;
for (ll div = 2LL; div * div <= num; div = div % 2 == 0 ? div + 1LL : div + 2LL) {
while (num % div == 0) {
cout << div << '\n';
num /= div;
}
}
if (num > 1) {
cout << num << '\n';
}
return 0;
}
'BOJ_단계별로 풀어보기(9단계~) > [8단계] 기본 수학2' 카테고리의 다른 글
[백준 4948] 베르트랑 공준 (0) | 2021.07.25 |
---|---|
[백준 1929] 소수 구하기 (0) | 2021.07.25 |
[백준 2581] 소수 (0) | 2021.07.25 |
[백준 1978] 소수 찾기 (0) | 2021.07.25 |
소수 문제 해결의 기본 (0) | 2021.07.24 |