문제
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
출력
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다.
예제 입력 1
72 |
예제 출력 1
2 2 2 3 3 |
예제 입력 2
3 |
예제 출력 2
3 |
예제 입력 3
6 |
예제 출력 3
2 3 |
예제 입력 4
2 |
예제 출력 4
2 |
예제 입력 5
9991 |
예제 출력 5
97 103 |
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
bool isPrime(int N)
{
if(N<2)
return false;
else if(N==2)
return true;
else if(N%2==0)
return false;
else
for(int i=3;i*i<=N;i+=2)
if(N%i==0)
return false;
return true;
}
void divide(int N)
{
for(int i=2;i<=N;i++)
if(N%i==0)
if(isPrime(i))
{
printf("%d\n", i);
N/=i;
i--;
}
if(N!=1)
printf("%d\n", N);
}
int main(void)
{
int N;
scanf("%d", &N);
divide(N);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 14659번: 한조서열정리하고옴ㅋㅋ (0) | 2020.09.02 |
---|---|
<백준 알고리즘> 10708번: 크리스마스 파티 (0) | 2020.09.02 |
<백준 알고리즘> 1427번: 소트인사이드 (0) | 2020.09.01 |
<백준 알고리즘> 15953번: 상금 헌터 (0) | 2020.08.30 |
<백준 알고리즘> 10569번: 다면체 (0) | 2020.08.30 |