https://www.acmicpc.net/problem/11653
11653번: 소인수분해
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
www.acmicpc.net
N의 최대 크기가 천만이다.
간단하게 생각해서 N을 2부터 나눠본다. 더이상 2로 나눠지지 않으면 3으로 나눠본다. 더이상 3으로 나눠지지 않으면 4로 나눠본다...
위의 과정을 반복한다.
#include <iostream>
int main() {
int number, prime = 2;
scanf("%d", &number);
while (number > 1) {
if (number % prime > 0) {
prime++;
}
else {
printf("%d\n", prime);
number /= prime;
}
}
}
나눗셈에서 나머지가 있을 때만 분모를 증가시킨다. number가 1 이상일 때만 나눗셈을 할 수 있으므로 조건을 저렇게 설정했다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
1262 알파벳 다이아몬드 (0) | 2022.08.20 |
---|---|
9020 골드바흐의 추측 (0) | 2022.08.19 |
1018 체스판 다시 칠하기 (0) | 2022.08.19 |
2293 동전 1 (0) | 2022.08.17 |
11726 2xN 타일링 (0) | 2022.08.16 |
댓글