자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_에라토스테네스 체)

https://cote.inflearn.com/contest/10/problem/02-05

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

 

5. 소수(에라토스테네스 체)

 

예시 입력 1 

20

예시 출력 1

8

내가 푼 풀이(Time: 198ms Memory: 27MB)

1. boolean 배열을 입력값 n보다 +1한 크기로 만듭니다

   1-1. boolean의 기본값인 false로 저장됩니다

   1-2. n+1을 한 이유는 n까지 소수인지를 체크하기 위함이고, 인덱스값 +1해야지 n번까지 검토할 수 있습니다

2. true이면 소수, 먼저 2부터 true로 다 세팅해줍니다

3. 2의 배수, 3의 배수가 n이랑 같아질때까지 순회하는 for문을 만들어줍니다

   3-1. boolean 배열이 true일 경우, i * i한 숫자부터 n까지 배수를 false로 변경해줍니다.

   3-2. 2와 3은 소수 이기 때문에 제외하고 다음 배수부터 false로 변경하면 됩니다.

// 맨 처음 세팅
[false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
// 소수가 아닌걸 false로
[false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false]

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

public class Main {

    public int solution(int n) {
        boolean[] isPrime = new boolean[n + 1];

        int answer = 0;

        // 초기화: 모든 수를 소수로 가정하여 isPrime 배열을 true로 초기화합니다.
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체 알고리즘을 사용하여 소수를 찾습니다.
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 소수의 개수를 세어서 반환합니다.
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                answer++;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(T.solution(num));
    }

}

 

 

강의 풀이(Time: 157ms Memory: 28MB)

 

제곱근으로 하는 것도 에라토스테네스 체 보다 소수를 구하는데  느리다.

그래서 에라토스테네스 체 로 꼭 해야합니다. 2중 for문으로 하면 20만 넘은 경우 time limit이 날 것이다.

 

1. int[] ch = new int[21] 로 해야지, 인덱스 번호가 20번까지 생깁니다.

2. 동적 배열은 0으로 초기화됩니다.

3. 소수가 0이면 카운팅 합니다.

 

2의 배수는 1과 자기 자신 말고도 2라는 약수를 갖는다는 의미. 2를 약수로 갖는다는 건 소수가 아니다.

import java.util.Scanner;

public class Main {

    public int solution(int n) {
        int answer = 0;
        int[] ch = new int [n+1];
        for (int i = 2; i <= n; i++) {
            if (ch[i] == 0) {
                answer++;
                // 카운팅 하고 나서 배수를 1로 변경
                // i의 배수로 j가 돌아야 하기 때문에 j=j+i, i만큼 증가해야 한다.
                for (int j = 0; j <= n ; j=j+i) ch[j] = 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(T.solution(n));
    }
}

 

1. 첫 번째 코드 (에라토스테네스의 체 사용):
   • 첫 번째 코드는 에라토스테네스의 체 알고리즘을 사용하며, 주어진 범위 내에서 소수를 찾는 데 효율적입니다.
   • 각 인덱스가 숫자를 나타내는 isPrime 배열을 초기화하며 초기에 모든 숫자가 소수로 가정됩니다.
   • 2부터 시작하여 각 소수의 배수를 반복적으로 소수가 아닌 것으로 표시합니다.
   • 마지막으로 소수로 표시된 숫자를 세어 반환합니다.
   성능 설명:
   • 에라토스테네스의 체 알고리즘은 소수의 배수를 제거하므로 반복 횟수가 상당히 감소합니다.
   • n까지의 모든 소수를 찾는 데 O(n*log(log(n)))의 시간 복잡도를 가집니다.
   • 주요 루프는 2부터 n까지 모든 숫자에 대해 실행되며, 내부 루프는 더 적은 횟수로 실행되므로, 특히 큰 n 값에 대해서 효율적입니다.
2. 두 번째 코드 (소수 카운팅 사용):
   • 두 번째 코드는 카운팅 접근 방식을 사용하며, 숫자가 소수로 표시되었는지 (0) 아니면 아닌지 (1)를 나타내는 배열 ch를 초기화합니다.
   • 2부터 시작하고 각 소수를 찾을 때마다 answer를 증가시키고, 그 배수를 소수가 아닌 것으로 표시하기 위해 ch[j] = 1을 설정합니다.
   성능 설명:
   • 이 접근 방식은 하나씩 소수를 세고, 2부터 n까지 모든 숫자를 반복적으로 확인해야 합니다.
   • 찾은 각 소수에 대해 내부 루프를 실행하여 그 배수를 표시해야 하며, 큰 n 값에 대해 많은 연산을 수행해야 합니다.
   • 시간 복잡도는 O(n^2)로, 입력 숫자 n에 대해서는 성능이 떨어집니다.

요약하면, 첫 번째 코드가 정수 n까지의 소수를 찾는 데 시간 복잡도 측면에서 더 효율적입니다. 이 코드는 에라토스테네스의 체 알고리즘을 사용하며, 소수의 배수를 제거하여 반복 횟수를 줄이므로 특히 큰 n 값에 대해서 더 빠릅니다. 반면 두 번째 코드는 하나씩 소수를 세고, 제곱 수의 배수를 확인하기 위해 내부 루프를 실행하므로 입력 값이 큰 경우 성능이 떨어집니다