[Java 자바] 백준 알고리즘 1929번 답 : 소수 구하기

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

1929번: 소수 구하기

 

 

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

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());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int [] isPrime = new int[N+1];

        for(int i=2;i<=N;i++){
            isPrime[i] = i;
        }

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

        for(int i=M;i<=N;i++){
            if(isPrime[i] != 0){
                sb.append(isPrime[i]+"\n");
            }
        }

        System.out.println(sb);
    }
}

 

문제 제목만 보고 소수? 쉽지~ 하고 덤볐다가ㅎ 큰 코 다친 문제,,ㅎ

 

정말 일반적인 소수 판별 알고리즘 썼다가 시간초과남,,^^

'보기'를 보니까 정수론, 에라토스테네스의 체 같은 제가 모르는 얘기가 나오길래

여기선 혼자 고민해도 답이 없다 판단하고 에라토스테네스의 체를 공부했음다.

 

다음 글에서 소수 판별에 대해 서술해보겠슴당