정수론 관련 문제들!

WOOK JONG KIM·2023년 5월 12일

코딩테스트_문제모음집

코테문제_모음집

목록 보기

10/12

에라토스테네스의 체

소수란 1과 자기 자신 외에 약수가 존재하지 않는다는 것을 의미

이러한 소수는 이렇게 구할수도 있을것이다

이중 for 문을 통해서 각 i가 2이상 i미만인 약수가 없는지 판단하고, 없으면 prime 리스트에 넣는 방법

하지만 이 경우에 시간복잡도가 O(N^2)이다

이보다 더 빠른 방법은 에라토스테네스의 체를 사용하는 것

에라토스테네스의 체는 이름에 체가 들어가 있듯이 체로 수들을 걸러내는 역할을 하는데, 1을 논외로 하고 합성수들을 걸러냄
-> 여기서 합성수란 약수가 3개 이상인 수
-> 이때 핵심 아이디어는 소수의 배수들을 죄다 걸러내는 것

우선 1을 소수가 아니므로 빗금을 치고 시작

만약 빗금이 쳐져있지 않은 수(ex:2)를 만나면 이를(ex:2)를 제외한 2의 배수에 전부다 빗금을 칠함

이어서 나온 3역시, 3보다 큰 3의 배수에 전부 빗금을 침
-> 이미 빗금이 쳐져 있는 칸은 무시해도됨(아마 6의 배수겠죠?)

이걸 계속해서 반복해서 50이하의 모든 소수에 대해 이 행동을 반복하면 최종적으로 50이하의 소수만 남기고 모두 빗금이 쳐져있게 됨

k번째 칸을 볼 때까지 빗금이 쳐져 있지 않다는 말은 1 이상 k 미만의 어떠한 수의 배수도 아니라는 뜻이기 때문에 소수인 것

표에 빗금을 치는 횟수를 대략적으로 따져보면 N/2 + N /3 .... N/(N-1) + N/N 정도가 됨
이러한 빗금 치는 횟수는 대략적으로 O(longN)의 상한과 비슷

에라토스테네스의 체 문제

문제1

https://www.acmicpc.net/problem/1929

가장 간단한 문제

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        int[] arr = new int[end+1];

        for(int i = 2; i <= end; i++){
            arr[i] = i;
        }

        for(int i = 2; i <= Math.sqrt(end); i++){
            if(arr[i] == 0){
                continue;
            }
            for(int j = i+i; j <= end; j = j+i){
                arr[j] = 0;
            }
        }

        for(int i = start; i <= end; i++){
            if(arr[i] != 0){
                System.out.println(arr[i]);
            }
        }
    }
}

여기서 처음에 왜 i <= Math.sqrt(end)를 수행하는지 이해하기 어려웠다.
이해하기 위해 chat GPT 활용

즉 예를 들어 15와, 9를 한번 생각해보자
이 둘이 a x b 형태로 표현될려면 3 x 5, 3 x 3이 있다
이때 특징을 살펴보면 무조건 두 숫자중 한 숫자는 sqrt(해당 숫자)이하이다.
-> 이하는 약수가 3개인 경우겠지?

문제 2

https://www.acmicpc.net/problem/1456

조금만 생각 잘해보면 풀수있는 문제다! 다만 자료형이 int 범위를 넘어설 수 있다는 것을 잘 생각해야 함

문제3

https://www.acmicpc.net/problem/1747

적당히 할만한 문젠데 도대체 범위를 어디까지 잡아야 하는지 미지수...

유클리드 호제법

원래라면 두 수의 최대 공약수를 소인수 분해를 이용해 구하였음
-> 하지만 유클리드 호제법은 이거 보다 좀더 간단

문제1(브론즈1)

https://www.acmicpc.net/problem/1934

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

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            int gcd = getGcd(num2, num1);
            int lcm = (num2 * num1) / gcd;
            bw.write(lcm + ""+"\n");
        }
        bw.flush();
        bw.close();
    }

    private static int getGcd(int a, int b) {
        if(b == 0){
            return a;
        }else{
            return getGcd(b, a % b);
        }
    }
}