소인수분해
•
1보다 큰 자연수를 소수인 인수들만의 곱으로 나타내는 것
•
합성수를 소수의 곱으로 나타내는 방법
1.
소수가 아닌 수를 계속 소수로 나눈다
2.
작은 소인수부터 차례로 나눈다
3.
몫이 소수가 되면 멈춘다
4.
나눈 소수들과 마지막 몫을 곱으로 나타낸다
•
몫을 나누었을 때 0이 되는 경우 해당 수를 출력한다
C
#include <stdio.h>
int main() {
int N, i, j;
scanf("%d", &N);
for (i = 2; i <= N; i++) {
while (N % i == 0) {
printf("%d\n", i);
N = N / i;
}
}
return 0;
}
C
복사
C++
#include <iostream>
using namespace std;
int main() {
int N, i, j;
cin >> N;
for(i = 2; i <= N; i++) {
while (N % i == 0) {
cout << i << endl;
N = N / i;
}
}
return 0;
}
C++
복사
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for(int i = 2; i <= N; i++) {
while(N % i == 0) {
System.out.println(i);
N = N / i;
}
}
}
}
Java
복사