BOJ) 소수 구하기

소수 구하기

1929번: 소수 구하기

풀이

 

소수를 구하는 문제를 풀어본지 오래돼서 에라토네스의 채 자체를 망각하고 있었다.

그래서 GCD를 통해 풀어야하나 생각하다가, 소수를 구하는 알고리즘이 있나 찾아봤다.

에라토네스의 채를 보고 존재가 다시 떠올랐다.

구현하는 방법은 까먹어서 방법을 익히기로했다.

 

1은 소수에 포함되지 않기 떄문에 2부터 시작하고, j에 해당하는 부분은 자신의 배수에 대해 표시를 해주는 것이다.

이후에, for문을 돌면서 소수를  찾아 출력해줬다.

 

하지만, for문을 다시 도는 부분이 불필요하다고 느껴져서, 처음 소수가 아닌 수들을 저장하는 과정에서 바로 소수를 출력해주었다.

결과적으로 훨씬 빠른 코드였다.

 

출력을 하는 방법의 차이기 때문에, 이것 보다는 에라토네스의 채를 기억에 남겨두는게 더 좋을 것 같다.

 

코드 1

 

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

public class FindPrimeNums_1929 {
    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());

        solution(start, end);

        br.close();
    }

    private static void solution(int start, int end) { // 1차 시도
        boolean[] prime = new boolean[end+1];
        prime[1] = true;
        for(int i= 2; i<=end; i++) {
            if(!prime[i]) {
                for (int j = i*2; j <= end; j+=i) {
                    prime[j] = true;
                }
            }
        }
        for(int i=start; i<=end; i++) {
            if(!prime[i]) {
                System.out.println(i);
            }
        }
    }
}

 

코드 2

 

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

public class FindPrimeNums_1929 {
    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());

        solution(start, end);

        br.close();
    }

    private static void solution(int start, int end) {  // 2차 시도, 더 효율적
        boolean[] prime = new boolean[end+1];
        final String newLine = "\n";
        StringBuffer sb = new StringBuffer();
        for(int i= 2; i<=end; i++) {
            if(!prime[i]) {
                if(i >=start) {
                    sb.append(i).append(newLine);
                }
                for (int j = i*2; j <= end; j+=i) {
                    prime[j] = true;
                }
            }
        }
        System.out.println(sb.toString());
    }
}