백준 11653 자바

 

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

<작성 답안>

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

int N = s.nextInt();


class nanugi{
void loof{}      
for(int i =2; i<N; i++){
   if(N%i == 0){
System.out.println(i);
int A= N/i;
      }
    }
return A;
}

if(A==-1)
 nanugi 
}
}

 

-> 객체지향 쓸려다가 망해부렸다..ㅋㅋㅋㅋㅋㅋㅋ 

정답 보니 쉬운 문제였다.

 

---

<정답>

 

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 <= Math.sqrt(N); i++) { // 또는 i * i <= N
while (N % i == 0) {
System.out.println(i);
N /= i;
}
}
if (N != 1) {
System.out.println(N);
}
}
}

 

---

<수정 및 보완>

    

먼저 아래와 같이 입력해서 컴파일 했더니... 출력 시간이 너무나 오래 걸린다... 

 

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

int N = s.nextInt();


for(int i =2; i<N; i++){ 
   while (N%i == 0){
System.out.println(i);
N = N/i;
    }
    }
if(N!=1) {
System.out.println(N);
}
}

}

---

출력시간을 단축시키기 위한 수학 공식.

 

어떤 N이 두 개이상 곱셈(인수)으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같다는 것이다.

 

즉, 반복문의 범위를 √N까지 반복하는 것이다.

 

그리고 이 때 중요한 점은, N /= i로 나누고 남은 최종 N이 두 가지 케이스로 나뉜다는 것이다.

 

예로들어 N = 16이 입력되었다고 가정해보자.

반복문으로 √N까지 한다고 하면 4까지 반복을 할 것이다.

그리고 처음 2에서 while문의 조건식을 만족(16 % 2 == 0)하면서 2를 출력한 다음 N을 2로 나누어 8이 되고, 다시 8 % 2 == 0 을 만족하므로 또다시 2를 출력한 뒤 N을 2로 나누어 4가 되고 이런식으로 쭉 가다가 마지막에 2 % 2 == 0 을 만족하여 2를 다시 한 번 출력한 뒤, N을 2로 나누어 1이 되고 while문 반복을 종료하게 된다. 그리고 1이 인수분해 되는 일은 없으므로 for문 또한 종료가 된다.

 

반대로 N = 34가 입력되었다고 가정해보자. 

반복문으로 √N까지 한다고 하면 근사값이 대략 5.83이므로 5까지 반복을 할 것이다.

그리고 처음 2에서 while문의 조건식 34 % 2 == 0 이므로 2를 출력한 다음 N을 2로 나눌 것이다. 그러면 17이므로 17 % 2 는 0이 아니기 때문에 while문은 종료된다. 그리고 for반복문 i값이 1씩 증가해서 검사하다가 i = 5 가 되면 종료가 되어버린다. 그렇게 되면 N은 17이라는 인수를 갖고 있는데 출력을 못하고 종료가 되어버리는 문제가 생긴다.

 

즉, for반복문을 종료하고 N이 1이 아니라면 N은 소수이자 인수인 것이 자명하기 때문에 한 번 더 출력해주는 조건문을 달아주어야 한다. 즉 다음과 같이 써야한다.

 

for(int i =2; i <Math.sqrt(N);v i++){
   if(N%i == 0){
       System.out.println(i);
        int A= N/i;  // N = N/i;

    }

}

 

if(N!=1)

System.out.println(N);

 

 

정답 및 풀이 출처 : https://st-lab.tistory.com/152