[백준] no1929: 소수 구하기

문제

: M과 N 사이의 수 중에 소수인 것을 모두 구하시오

(여기서 소수란, 1을 제외하고, 정수로 나누어 떨어지는 수가 자기 자신밖에 없는 수)

 

문제 링크 : https://www.acmicpc.net/problem/1929

---

풀이방법

1. 에라토스테네스의 체 (백준 풀이시 이걸로 통과 | 레퍼런스)

2. 이중반복 : 제곱근이 정수인 수 제거, 2는 미리 출력, 짝수 제거 => 이후 소수 판별

---

나의 코드 (시간초과)

1. 이중반복 방식 (ArrayList로 시도)

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class no1929 {
    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());
        ArrayList<Integer> list = new ArrayList<>();

        for(int i = M; i <= N; i++) list.add(i);

        if(list.get(0)==2) {
            list.remove(0);
            bw.write("2\n");
        }

        for(int i = 0; i < list.size(); i++) {
            if(list.get(i)%2==0) list.remove(i);
            else if(Math.sqrt(list.get(i))==Math.floor(list.get(i))) list.remove(i);
        }

        for(int i = 0; i < list.size(); i++) {
            int count = list.get(i);
            while(count-->0) {
                if(count%2==0) continue;
                if(count==1) {
                    bw.write(""+list.get(i)+"\n");
                    break;
                }
                if(list.get(i)%count==0) break;
            }
        }
        bw.close();
    }
}

2. 이중반복 방식 (일반 반복문 시도)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        for(int i =M; i <= N; i++) {
            if(i%2==0) {
                continue;
            }
            if(Math.sqrt(i)==Math.floor(i)) {
                continue;
            }
            if(i==2) {
                System.out.println(2);
                continue;
            }
            int count = i;
            while(count-->0) {
                if(count==1) {
                    System.out.println(i);
                    break;
                }
                if(i%count==0) break;
            }
        }
    }
}

 

---

레퍼런스 코드

: '에라토스테네스의 체'로 알고리즘

public class no1929 {

    // 에라토스테네스의 체 알고리즘 사용
    public static boolean[] prime;
    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());
        prime = new boolean[N + 1];
        get_prime();

        for(int i = M; i <= N; i++) {
            if(!prime[i]) bw.write(""+i+"\n");
        }
        bw.close();
    }

    public static void get_prime() {
        prime[0] = prime[1] = true;

        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) continue;
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

 

참고 링크 : https://st-lab.tistory.com/84