[BOJ/백준] 약수, 배수와 소수_ 11653번

1. 문제 번호 11653

 

 

 

 

 

---

 

 

 

 

 

2. 문제 풀이

 

 

한줄 평가

•   이게 브론즈 1이야? 난 왜 브론즈 2~3의 수학문제가 더 어렵냐 ..?
•   소인수분해의 성질을 외우자!!! (추가개념 참고)

 

 

 

문제를 먼저 정확히 파악

 

• 소인수분해
  • 어떤 N을 소수들의 곱으로 나타내는 것이다. 
    예를 들어 28을 소인수분해 하면 2*2*7 이다.
• 소수
  • 1과 자기 자신만을 약수로 가지는 수를 말한다.
    cf)에라토스테네스의 체

 

 

 

나의 문제풀이 방식 및 순서

 

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

 

1.  

 

 

 

 

 

 

---

3. 소스 인증

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        for(int i = 2; i <= Math.sqrt(N); i++){
            while(true){
                if( ( N % i) != 0) {
                    break;
                }else {
                    System.out.println(i);
                    N /= i;
                }
            }
        }
        if (N > 1) {
            System.out.println(N);
        }
    }
}

 

 

 

- 실패 소스코드 -

 

 

 

 

 

 

 

---

4.추가 개념

 

소인수분해의 성질

•  소인수분해에서 인수 중 하나는 반드시 sqrt(N)보다 작거나 같다.
  (근데 난 왜 이렇게 표현하는지 모르겠네..)
  (하나는 반드시 작거나 같다가 뭐야? 하나만 작거나 같다라는 뜻인가? 28 의 경우 2 * 2 * 7인데)
  
•  sqrt(N)보다 큰 인수는 최소 0개 최대 1개이다. (<<이게 더 깔끔하지 않나? 

 

 

왜 인수 중 하나는 반드시 sqrt(N)보다 작거나 같을까?

 

 소인수분해는 어떤 수 N을 소수의 곱으로 표현하는 것이다. N = 100 이면 100 = 2 × 2 × 5 × 5 의 소수의 곱으로 나타낸다.

 이를 이해하기 위해 다음을 확인해보자.

 

1. 인수의 성질
   •  N 을 두 개의 인수  a 와  b 로 나타낼 수 있습니다. 즉,  N = a × b .
   • 여기서  a 와  b 는  N 의 인수입니다.
   
   
2. 최대 인수의 크기
   • 만약  a 와  b 가 모두  sqrt(N) 보다 크다면, 두 인수의 곱  a × b 는  N 보다 커집니다. 이는  N 을 초과하므로 불가능합니다
   
   
3. 결론
   • 따라서  N 의 인수 중 적어도 하나는 반드시  sqrt(N) 보다 작거나 같아야 합니다.

 

그래서 sqrt(N) 까지의 소수만 고려하면 충분하다.

 

 

 

 

---

5. 참조 블로그

---

 

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

 

---