[Java] 백준 BOJ 1929: 소수 구하기

시간 때문에 많이 고생한 문제 -.-
for문의 범위에 관해서도 많이 고민했다.

 

아이디어

1. 원소 값과 인덱스가 일치하는 배열을 만들기 위해 n+1 사이즈 배열에 각 값을 넣는다.
2. 2부터 루트 n까지의 범위를 가지는 1차 for을 돌린다. 이것은 배열에서 2의 배수, 3의 배수, ..., i의 배수를 지우기 위해 돌리는 for문이다. 이때 기호로 i를 사용하며, 이것을 배열의 인덱스 번호로 생각한다.
(*에라토스테네스의 체는 소수의 배수를 지우는 방식으로 동작한다. 예시로 어떤 수가 i*j(i<j)라면 이 수는 i*i보다 크고 j*j보다 작은데, for의 범위를 j까지로 늘리지 않아도 i의 for에서 충분히 처리할 수 있으므로 상한을 루트 n으로 정한다.)
3. 이 배열에서 인덱스와 원소 값은 일치하므로 인덱스가 i의 배수인 원소의 값을 0으로 만든다. 이때 i 자체는 제외하고 i*2부터 시작한다. 또한, 이미 인덱스가 i인 원소의 값이 0이면(=소수가 아니면) 패스하고 다음 i로 넘어간다.
4. 값이 0이 아닌 원소들만 찾아서 출력한다. 이때, 1을 제외해야 한다.

 

정답 코드

import java.io.*;
import java.util.*;
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 m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] nums = new int[n+1];

        for (int i=0; i<=n; i++) { // 배열 초기화
            nums[i] = i;
        }

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

        StringBuffer sb = new StringBuffer();

        for (int i=m; i<=n; i++) {
            if (nums[i] != 0 && nums[i] != 1) {
                sb.append(i+"\n");
            }
        }

        bw.write(sb.toString());

        br.close();
        bw.flush();
        bw.close();
    }
}

 

틀린 코드

시간 초과 1 - 에라토스테네스의 체 아이디어 기반이긴 하나 약간 응용한 버전

import java.io.*;
import java.util.*;
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 m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        List<Integer> nums = new ArrayList<>();

        for (int i = m; i <= n; i++) {
            nums.add(i);
        }

        for (int j=2; j<=Math.sqrt(n); j++) {
            for (int i=0; i<nums.size(); i++) {
                if (nums.get(i) == 1 || nums.get(i)%j == 0 && nums.get(i)/j>=2) {
                    nums.remove(nums.get(i));
                }
            }
        }

        for (int i : nums) {
            bw.write(Integer.toString(i));
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

시간 초과 2 - 에라토스테네스의 체

import java.io.*;
import java.util.*;
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 m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        List<Integer> nums = new ArrayList<>();

        for (int i = m; i <= n; i++) {
            nums.add(i);
        }

        if (nums.contains(1)) {
            nums.remove(Integer.valueOf(1));
        }

        for (int i=2; i<=Math.sqrt(n); i++) {
            for (int j=i; j<=n/i; j++) {
                if (nums.contains(i*j)) {
                    nums.remove(Integer.valueOf(i*j));
                }
            }
        }

        for (int i : nums) {
            bw.write(Integer.toString(i));
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

참고

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