📌 정수론 : 정수의 성질을 연구하는 분야

🎯 약수(Divisor) : 특정 수를 나누어 떨어지게 하는 수

import java.util.*;
import java.io.*;
 
/*
  -> 정수 하나를 입력받아 약수를 출력하는 로직
  
  // 입력
  20
  // 출력
  1 2 4 5 20
  
*/
 
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    
    for(int i = 1; i <= n; i++) {
      // 숫자 i가 n의 약수인지 판단
      if(n % i == 0) {
        System.out.print(i + " ");
      }
    }
 
  }
}

 

관련 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/120897

🎯 소수(Prime number) : 약수가 1과 자기 자신뿐인 수

import java.util.*;
import java.io.*;
/*
  ** 소수 판별
  1, [2, 3, 4, 5, 6], 7 
  ->1과 자신을 제외한 숫자중 7과 나누었을 때 나누어 떨어지는게 있으면 소수가 아니다.
  
  입력 : 8
  출력 : NO
  
  입력 : 7
  출력 : YES
  
*/
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());    
    
    int n = Integer.parseInt(st.nextToken());
    boolean flag = true;    
    for(int i = 2; i <= n-1; i++) {
      if(n % i == 0) {
        flag = false;
        break;
      }
    }
    
    if(flag) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
 
  }
}

 

관련문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12977

🎯 에라토스테네스의 체 : 소수를 구하는 방법 중 하나

• 배수를 제거하면서 소수를 구하는 방식

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

-> 1을 제외한 가장 작은 수 2를 선택 후 2는 소수라고 판정.
-> 2의 배수들은 모두 소수가 될 수 없으므로 제외
-> 그 다음 작은 수 3을 선택
-> 3의 배수들을 모두 소수가 될 수 없으므로 제외
-> 그 다음 작은 수 5를 선택
-> 5의 배수들을 모두 소수가 될 수 없으므로 제외
. . .

**시간복잡도 : nlogn => 빠르다
- 1~n까지의 자연수 중 모든 소수를 구할 때 적합
- n이 소수인지를 판단할 때는 부적합

 

import java.util.*;
import java.io.*;
/*
  ** 에라토스테네스의 체
  
  입력 : 50
  출력 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
 
*/
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
  
    int n = Integer.parseInt(st.nextToken());
    int[] arr = new int[n+1];
    arr[0] = 1;
    arr[1] = 1;
    
    for(int i = 0; i < n+1; i++) {
      if(arr[i] == 0) {
        System.out.print(i + " ");
        for(int j = i; j < n+1; j++) {
          if(j%i == 0) {
            arr[j] = 1;
          }
        }
        
      }
      
    }
 
  }
}

 

- 개선버전

void 에라토스테네스의체() {
 
        int n = 10; 
        boolean[] isPrimes = new boolean[n + 1];
        Arrays.fill(isPrimes, true);
 
        isPrimes[0] = false;
        isPrimes[1] = false;
 
        for ( int i = 2; i*i <= 10; ++i ) {
            if ( isPrimes[i] ) {
                for ( int j = i*i; j <= n; j+=i ) {
                    isPrimes[j] = false;
                }
            }
        }
 
    }

 

관련문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12921

🎯 소인수 분해(Prime factorization) : 숫자 n을 소수의 곱으로 나타냄

• 2부터 시작해서 나누어 본다. 2로 또 나누어지면 나누어 떨어지지 않을 때까지 나누어보고 3으로 넘어간다.
• 소수가 아닌 4로 왔을 때는 4도 2의 원소(2*2)이기 때문에 절대 나누어 떨어질 수 없다. 즉 소수 신경쓰지 않고 정수로 계속 나누아가면 된다.

import java.util.*;
import java.io.*;
 
/*
  소인수 분해 출력
  
  입력 : 60
  출력 : 2 2 3 5
  
*/
 
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken());
    
    // n == 1 이면 끝난다.
    for(int i=2; n>1;) {
      if(n%i == 0) {
        System.out.print(i + " ");
        n /= i;
      } else {
        i++;
      }
    } 
 
  }
}

 

🚀 공약수와 공배수(Common Divisor and Common Multiplier)

• A와 B의 공약수 : A의 약수이면서 동시에 B의 약수인 수

8 36
-> 1, 2, 4

• A와 B의 공배수 : A의 배수이면서 동시에 B의 배수인 수

8 36
-> 72, 144, ...

 

🚀 최대공약수와 최소공배수(Greatest Common Divisor and Lower Common Multiplier)

• A와 B의 최대공약수(GCD) : A의 약수이면서 동시에 B의 약수인 수 중 최댓값

8 36
-> 4

• A와 B의 최소공배수(LCM) : A의 배수이면서 동시에 B의 배수인 수 중 최솟값

8 36
-> 72

 

관련문제 : https://school.programmers.co.kr/learn/courses/30/lessons/120852

🎯 유클리드 호제법 : 최대공약수를 구하기 위한 알고리즘

152 68 의 최대 공약수를 구하는 원리.

a           b         r(a를 b로 나눈 나머지) 
152       68        20
68         20        8
20          8         4
8            4         0
=> 4가 최대 공약수이다.

 

import java.util.*;
import java.io.*;
 
/*
  유클리드 호제법
  
  두 정수의 최대공약수/최소공배수를 출력.
  
  입력 : 156 86
  출력 : 2 6708
*/
 
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int A, B; // 최소공배수 구할 때 사용할 원본
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    A = a;
    B = b;
    
    int GCD = -1; // 최대공약수
    int LCM = -1; // 최소공배수
    
    while(true) {
      
      int r = a % b;
      if(r == 0) {
        // 최대공약수
        GCD = b;
        break;
      }
      
      a = b;
      b = r;
    }
    // 최소공배수
    LCM = (A / GCD) * (B / GCD) * GCD;
    
    System.out.println(GCD + " " + LCM);
  }
}

 

관련문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12940

🎯 파스칼의 삼각형 => 조합과 관련

 

 

문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.
n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.  

입력

첫째 줄에 정수 n, m(0 ≤ m ≤ n ≤ 30)이 들어온다.

출력

첫째 줄에 nCm의 값을 출력한다.

---

예제 입력

5 2

예제 출력

10

 

import java.util.*;
import java.io.*;
 
public class Main{
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    
    if(n > 0) {
      // 파스칼 삼각형을 만든다.
      // 열의 개수는 다르다.
      int[][] pascal = new int[n+1][];
      
      // 파스칼 삼각형의 0행
      pascal[0]    = new int[1];
      pascal[0][0] = 1;
      // 파스칼 삼각형의 1행
      pascal[1]    = new int[2];
      pascal[1][0] = 1;
      pascal[1][1] = 1;
      
      for(int row = 2; row < n+1; row++) {
        pascal[row] = new int[row+1];
        // 파스칼 삼각형해서 처음과 끝은 항상 1이다.
        pascal[row][0]   = 1; 
        pascal[row][row] = 1;
        // 중간의 값을 규칙에 맞게 채워 준다.
        for(int col = 1; col < row; col++) {
          pascal[row][col] = pascal[row-1][col-1] + pascal[row-1][col];
        }
      }
      // 답
      System.out.println(pascal[n][m]);
    } else {
      System.out.println(1);
    }
    
  }
}