[ 정수론 ] 소수 구하기, 오일러피, 유클리드 호제법(백준 1929)

 소수 구하기

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수.

1과 자기 자신 외에 약수가 존재하지 않는 수!

 

💡  소수 구하기의 핵심 이론 - 에라토스테네스의 체 원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지원지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력한다.

☝🏻 에라토스테네스의 체 원리의 시간복잡도는 최적화의 정도에 따라 다르지만 일반적으로 O(Nlog(logN))이다! 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다!!

 

 1929 : 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

입력	출력
3 16	3 5 7 11 13

 

문제 풀이

• N의 최대 범위가 100만이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간초과가 발생한다. 따라서 에라토스테네스방법으로 문제를 풀어야한다.
• 에라토스테네스로 풀때 마지막값의 제곱근까지만 판별한다. 제곱근 X 제곱근보다 큰 값 은 될 수 없기때문
  Math.sqrt()사용해서 제곱근 구현

 

실행 코드

import java.util.Arrays;
import java.util.Scanner;

public class P13430_decimal {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //시작
        int M = sc.nextInt(); //끝
        int[] A = new int[M+1];
        Arrays.setAll(A, i -> i); //1~m까지 숫자 채우기

        // 에라토스테네스 원리
        for(int i=1;i<=Math.sqrt(M);i++) {
            if(A[i]==1) { //1은 제외
                A[i] = 0; // 배열에서 지우는걸 0으로 대체
                continue;
            }else if(A[i]==0){ //이미 제거된건 제외
                continue;
            }else{
                for(int j=2;;j++){
                    if(i*j<=M){
                        A[i*j] = 0; //본인을 제외하고 배수들을 제거
                    }else{
                        break;
                    }
                }
            }
        }
        for(int i=N;i<=M;i++) {
            if(A[i]!=0) {
                System.out.println(A[i]);
            }
        }
    }
}

 

 

 

 유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 사용한다.

 

💡  유클리드 호제법의 핵심 이론 - MOD연산을 이해해야한다!(나머지 연산)

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 단계 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

 1934 : 최소공배수

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

 

 

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

입력	출력
3 1 45000 6 10 13 17	45000 30 221

 

문제 풀이

• 최소공배수 = A x B / 최대공약수

 

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1934_Euclidean {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int LCM = Euclidean(a, b); // least common multiple
            System.out.println(a*b/LCM);
        }
    }

    private static int Euclidean(int a, int b) {
        // 만약 b가 더 크더라도 재귀로 Euclidean(b, a)가 실행됨
        if(b==0){
            return a;
        }
        return Euclidean(b, a%b);
    }
}

 

 

 오일러 피 - 서로소

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

서로소란 공약수가 1밖에 없는 두 수를 말한다.

예를들어 1과 6의 서로소는 1 2 3 4 5 6  ->  P[6] = 2

💡  오일러 피의 핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다.(i는 K의 배수)
3. 배열의 끝까지 2를 반복한 후 배열에서 남아있는 모든 수를 출력한다.

☝🏻 간단한 오일러 피 구하는 코드

import java.util.Arrays;
import java.util.Scanner;

public class disjoint {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] A = new int[m+1];
        Arrays.setAll(A, i -> i);

        for (int i = 2; i <= m; i++) {
            if(A[i]==i){
                for (int j = 1; i*j <= m; j++)
                    A[i*j] = A[i*j] - A[i*j]/i;
            }
        }
        System.out.println(A[m]);
    }
}