백준 1929번 소수 구하기(Java)

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

1929번: 소수 구하기

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

이 문제는 주어진 구간에 해당하는 소수를 찾는 문제인데 일반적으로 반복문을 이용해서 푼 후 에라토스테네스의 체라는 알고리즘을 알게 되어 2가지 방법으로 풀어 보았다.

 

소수(Prime Number)는 1보다 큰 자연수 중 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 자연수이다.

 

즉 소수의 약수는 2개만을 가지며 그 중 하나는 반드시 1이며, 나머지 자기 자신만을 약수로 갖기 때문에 1보다 크고 자기 자신의 수보다 작은 약수로 갖게 된다면 이는 합성수라고 한다.

그리고 위의 개념을 확장해본다면 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수로 이루어진 곱으로 표현할 수 있다.

그리고 이를 소인수분해라고 한다.

소수는 1과 자기 자신만을 약수로 갖고, 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수들로 이루어진 곱으로 표현할 수 있다고 했다.

1 보다 큰 자연수는 모두 소수 또는 합성수로 이루어져 있으니 1 보다 큰 모든 자연수는 소수들의 곱으로 표현할 수 있다.

 

이제 소수에 대한 정의를 보았으니 소수를 구하는 알고리즘을 보겠습니다.

 

방법1

임의의 수 N이 1과 N을 제외한 다를 수를 약수로 가지고 있다면 그 수는 소수가 아니고, 만약 다른 약수가 없다면 그 수는 소수이다.

그 중 1부터 √N 이하의 자연수들만 나누는 방법으로 왜 √N 이하의 자연수까지만 나누어 보는지는 생각해보면 소수를 판별하기 위해서는 결국 1과 자기 자신을 제외한 다른 자연수를 약수로 가지고 있으면 안된다.

 

임의의 자연수 𝐍 (𝐍 > 0) 이 있다고 가정하자.

 𝑝 × 𝑞 = 𝐍 을 만족할 때 우리는 아래와 같은 부등식을 완성할 수 있다.

 

( 1 ≤  𝑝 , 𝑞 ≤ 𝐍 )

 

그리고 p와 q 중 하나는 √N 보다 작거나 같다.

 

예로 N = 16 이라고 하자.

그러면16은 아래와 같이 두 수의 곱으로 표현 할 수 있다.

1 x 16

2 x 8

4 x 4

8 x 2

16 x 1

여기서 볼 수 있듯이 만약 𝑝 가 증가한다면 자연스레 𝑞 가 감소하고,

반대로 𝑝 가 감소한다면 자연스레 𝑞 가 증가한다.

 

그리고 𝑝 와 𝑞 는 𝐍의 약수이기 때문에 결국 𝐍 을 임의의 수로 나누게 되면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수 밖에 없다.

 

결과적으로 𝑝 와 𝑞 중 하나는 반드시 √N 보다 작거나 같다.

 

즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다.

 

이런 방법으로 위 백준 소수 구하기 문제를 풀어보았다.

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * 백준 https://www.acmicpc.net/problem/1929
 * Silver2
 * 소수 구하기
 */
public class Main {
    public static int findPrimeNumber(int n) {
        if (n == 1){
            return 0;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return 0;
            }
        }
        return n;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String in = br.readLine();
        String[] testcase = in.split(" ");
        int start = Integer.parseInt(testcase[0]);
        int end = Integer.parseInt(testcase[1]);

        List<Integer> primes = new ArrayList<>();

        for (int i = start; i <= end; i++) {
            int prime = findPrimeNumber(i);
            if (prime != 0) {
                primes.add(prime);
            }
        }
        primes.forEach(System.out::println);
    }
}

위 코드는 findPrimeNumber 메서드안에서 √N 이하의 자연수까지만 나누어 약수인지 판별한다.

 

방법2

 : 에라토스테네스의 체

 

소수를 구하는 대표적인 방법 중 하나다.

" k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다"

 

즉, 방법으로 보면 다음과 같다.

출처 : https://st-lab.tistory.com/81

 

k = 2 이면 2 를 제외한 2의 배수를 모두 지워주고,

k = 3 이면 3 을 제외한 3의 배수를 모두 지워주고,

(4는 이미 k = 2 에서 제외되어 넘어간다.)

k = 5 이면 5 를 제외한 5의 배수를 모두 지워주고..

 

이렇게 하여 k = √N 까지 반복하는 방법이다.

 

이 방법은 소수를 구하는 방법이랑 판별하는 방법이 동일하기 때문에 하나로 묶어서 설명하겠다.

 

[ N 이하의 모든 소수를 구하는 알고리즘 ]

 

import java.util.Scanner;
 /**
 * 출처 : https://st-lab.tistory.com/81
 */
public class Prime_3 {
 
    public static boolean[] prime;	// 소수를 체크할 배열
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		
		make_prime(N);
 
		for(int i = 0; i < prime.length; i++) {
			if(prime[i] == false) {	// 소수(false)일 경우 출력
				System.out.println(i);
			}
		}
	}
 
	// N 이하 소수 생성 메소드 
	public static void make_prime(int N) {
		
		prime = new boolean[N + 1];	// 0 ~ N
 
		/*
		소수가 아닌 index = true
		소수인 index = false
		*/
		
		// 2 미만의 N 을 입력받으면 소수는 판별할 필요 없으므로 바로 return
		if(N < 2) {
			return;
		}
        
		prime[0] = prime[1] = true;
		
        
		// 제곱근 함수 : Math.sqrt()
		for(int i = 2; i <= Math.sqrt(number); i++) {
        
			// 이미 체크된 배열이면 다음 반복문으로 skip
			if(prime[i]==true) {
				continue;
			}
        
			// i 의 배수들을 걸러주기 위한 반복문
			for(int j = i*i; j < prime.length; j = j+i) {
				prime[j] = true;
			}
		}
 
	}
 
}

 

언뜻 보기에는 이중for문이라 시간복잡도가 O(N²) 일 것 같지만 그렇지 않다.

 

1 ~ 𝑥 까지의 수가 있는 칸을 체크하는 횟수를 대략적으로 따진다면 아래와 같을 것이다.

(k = 2 부터 시작한다고 할 때)

 

(𝑥/2) + (𝑥/3) + (𝑥/4) + (𝑥/5) + (𝑥/6) + ⋯ + (𝑥/𝑥-1) 

 

그리고 N 이 무한대일 때, 우리는 𝑥∑ (1/𝑥) 을 적분으로 변환할 수 있다.

즉, 𝑥 ∫ (1/𝑥)𝑑𝑥 가 된다.

 

그리고 𝑥 ∫ (1/𝑥)𝑑𝑥 = 𝑥 𝑙𝑛𝑥 라는 것을 알 수 있다.

 

 

즉, N 이하의 소수에 대하여

단순하게 체에 거르는 것만 해도 시간 복잡도는 O(N㏒N) 이다.

( ㏒ 는 자연로그 𝑙𝑛 으로 본다 )

 

그런데 우리는 여기서 더 나아가 이미 체크된 배열은 검사하지 않고 다음 반복문으로 넘어간다.

(𝑥/2) + (𝑥/3) + (𝑥/4) + (𝑥/5) + (𝑥/6) + (𝑥/7)+ (𝑥/8)+ (𝑥/9) + ⋯ + (𝑥/𝑥-1) 

 

 

이에대한 시간복잡도는 '소수 정리' 와 조화수열, 테일러급수를 알아야한다만...

 

 

일단 대략적으로 말하자면 

'𝑥 보다 작은 소수의 개수가 대략 (𝑥 / ㏒𝑥) 개 있다'는 것이다.

 

이를 수식적으로 증명하기에는 시간이 너무 오래걸리니..

 

대략적으로 설명하겠다.

'𝑥 보다 작은 소수의 개수가 대략 (𝑥 / ㏒𝑥) 개 있다' 는 의미는

어떤 정수 𝑥 가 소수일 확률은 1 / ㏒𝑥 에 가깝다.

 

이를 조금만 변형해서 말하자면 다음과 같다.

 

'소수 간의 간격의 평균은 ㏒𝑥 가 된다.'

 

 

 

그럼 에라토스테네스의 체에 적용해보자.

위 방식은 N 이하의 모든 소수를 구하는 것이다.

 

그리고 체에 거르는 시간복잡도는 O(N㏒N) 이다.

 

그런데 우리는 이미 체크된 수, 즉 4, 6, 8, 9 ⋯ 은 검사하지 않고 건너뛴다.

 

위 if (prime[i] == true) 가 바로 그 코드다.

 

이미 체크된 배열은 continue 로 다음 턴으로 바로 넘어가버린다.

즉, 소수의 배수만 체크를 한다는 의미다.

 

소수정리에 의해 소수간의 평균 거리는 ㏒N 이고 밀도는 역으로 1/㏒N 이므로

시간 복잡도 = O(N㏒(㏒N)) 가 된다.

 

이를 이용하여 문제를 풀면 아래와 같이 풀어 볼 수 있다.

package BOJ;

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

/**
 * 백준 https://www.acmicpc.net/problem/1929
 * Silver2
 * 소수 구하기
 * 에라토스테네스의 체
 */
public class Main2 {
    public static boolean primes[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int start = Integer.parseInt(in[0]);
        int end = Integer.parseInt(in[1]);
        primes = new boolean[end+1];
        StringBuilder sb = new StringBuilder();

        setPrimes();
        for (int i = start; i <=end; i++) {
            if (!primes[i]){
                sb.append(i+"\n");
            }
        }
        System.out.println(sb);
    }
    public static void setPrimes(){
        primes[0] = primes[1] = true;
        for (int i = 2; i <=Math.sqrt(primes.length); i++) {
            if (primes[i]){
                continue;
            }
            for (int j = i*i; j < primes.length; j += i) {
                primes[j] = true;
            }
        }
    }
}

 

---

참고 및 출처 :

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

https://st-lab.tistory.com/84

[백준] 1929번 : 소수 구하기 - JAVA [자바]

 

https://www.geeksforgeeks.org/how-is-the-time-complexity-of-sieve-of-eratosthenes-is-nloglogn/?ref=rp 

How is the time complexity of Sieve of Eratosthenes is n*log(log(n))? - GeeksforGeeks