[백준 1929번] 정수론(Java)

소수(prime number)는 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다.

 

에라토스테네스의 체 원리

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

이중 for문을 이용하므로 O(N²) 정도라고 판단할 수 있다.

하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만

일반적으로 O(Nlog(logN))이다.

그 이유는 배수를 삭제하는 연산으로

실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

 

 

N의 제곱근까지 탐색하는 이유

어떤 수가 소수인지 판단할 때 그 수의 제곱근 이상을 확인할 필요가 없다.
예로, 100이 소수인지 확인할 때 10 이상의 배수는 확인할 필요가 없다.
제곱근 n보다 큰 수는 이 전에 이미 작은 수의 배수로 지워지기 때문에, 제곱근까지만 확인하면 된다.

 

037. 소수 구하기(백준 1929번)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n + 1];
        for(int i=2; i<=n; i++) {
            isPrime[i] = true;
        }

        for(int i=2; i<=Math.sqrt(n); i++){
            if(!isPrime[i]) continue;
            for(int j=i*i; j<=n; j+=i){
                isPrime[j] = false;
            }
        }

        for (int i = m; i <= n; i++) {
            if (isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

 

 

 

오일러 피

1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

ex. P[6] = 1~6 범위에서 6과 서로소인 자연수 개수 => 2 (1, 5가 있다)

 

 

유클리드 호제법

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

 

270과 192의 최대 공약수를 유클리드 호제법으로 찾아보는 그림