[JAVA] 백준 1929 소수 구하기

 

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

1929번: 소수 구하기

---

클래스2++도전기 

나만의 문제접근방법

1. 소수는 약수가 1과 그수 자신인 숫자라고 알고 있었다.

2. 시작이 3 끝이 16이면 3부터 반복문을통해 일차원적으로 소수인지 아닌지 검토하는 방식

-> 시간초과 메모리간당간당

3. 뭔가 알고리즘이 있을것같아 찾아보니 에라토스테네스의 체라는 알고리즘을 사용하거나 더 뛰어난 알고리즘을 사용해야했었다.

4. 간단히 공부 후 코드를 작성해 제출했음

 

 

어려웠던 점

출력해줄때 0,1을 예외처리해주지않아서 약 90%에서 계속틀려서 내가 알고리즘을 잘 못푼줄알았다.

항상 범위 끝과 끝에 오류가있고 그건 내손으로 만들었다.

import java.io.*;
import java.util.*;
public class boj1929 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(stz.nextToken());
		int m = Integer.parseInt(stz.nextToken());
		int arr[] = new int[m+1];
        double check = Math.sqrt(m+1);
	    for (int i = 2; i <= check; i++) {
	        if (arr[i] == 0) {
	            for (int j = 2; j*i <= m; j++) {
	                arr[i*j] = 1;
	            }
	        }
	    }
        arr[0] = 1;
        arr[1] = 1;
        
	    for (int i = n; i <= m; i++) {
	        if (arr[i] == 0) sb.append(i).append("\n");;
	    }
	    
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
	}
}