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

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

• 에라토스테네스의 체
  • 소수를 구하는 대표적인 방법
  • k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다

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

public class Main {
        // true: 소수 아님, false: 소수
        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];   // 0~N까지의 인덱스를 가진 boolean 배열 초기화
        getPrime();
        
        for (int i=M; i<=N; i++) {
            if (!prime[i]) bw.write(i+"\n");    // false일 경우 출력
        }
        bw.close();
    }
    
    // 에라토스테네의 체
    public static void getPrime() {
        prime[0] = prime[1] = true;

        // 2 부터 √N 이하까지 반복하여
        for (int i=2; i<=Math.sqrt(prime.length); i++) {
            
            if (prime[i]) continue; // 이미 체크한 인덱스면 continue

            // i의 배수
            for (int j=i*i; j<prime.length; j+=i) {
                prime[j] = true;
            }
        }
    }  
}

 

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

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

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

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

---

• 시간 초과

• 처음 접근한 방식 : 소수는 약수가 2개
  • for문이 두개면 O(n^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());
        int cnt;
        for (int i=M; i<=N; i++) {
            cnt = 0;
            for (int j=1; j<=i; j++) {
                if (i%j==0) cnt++;
            }
            if (cnt == 2) bw.write(i + "\n");
        }

        bw.close();
    }
}

---

시간복잡도 계산은 필수인데,,, 하기 시럿,,, 하지만 해야지