[백준] 1929번 소수구하기/에라토스테네스의 체 -자바(JAVA)

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

1929번: 소수 구하기

solved.ac에서 브론즈 문제만 건들이다가 맨 처음 건들인 실버 문제이다. 겁도없이 덤볐다가 꽤 고생했다.
시간초과가 떠버려서 내 코드가 틀린건지 맞는건지 알 수도 없는 상황이었다(ㅋㅋㅋ).
어쨌든 채점을 받기 위해선 먼저 시간을 줄여야 했다.

첫번째 시도 : M과 N 사이의 모든 수를 N 이하의 모든 수로 나누어보기

두번째 시도 : M과 N 사이의 모든 수를 N 이하의 모든 소수로 나누어보기

두번째 시도도 시간초과로 채점도 못했다 T^T

머리를 싸매다가 결국 구글링의 힘을 빌어보기로 타협했다.

 

에라토스테네스의 체 - 소수를 찾는 방법

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스의 체는 소수를 찾는 방법인데, 원리를 정리해보면 다음과 같다.

• M과 N 사이의 모든 수 중에서 2의 배수를 지운다.
• 지워지지 않고 남아있는 수 중에서 제일 작은 수의 배수를 지운다.(반복)

 

자연수들이 소수인지 아닌지 판단한 결과를 저장하기 위해서 자료형 중에선 boolean을 이용해 배열을 만들어줬다.

배열은 처음에 false로 초기화 한 후에, 에라토스테네스의 체를 통해 지워지는 수들은 데이터를 true로 바꾸어주고, 결과적으로는 false인 수들만 출력하게 하였다.

그 결과 다음 코드를 제출하고 드디어 통과했다 엉엉

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int M = scanner.nextInt();
		int N = scanner.nextInt();
		
		final int SIZE = 1000001;
		boolean array[] = new boolean[SIZE];
		Arrays.fill(array, false);
		
		array[1] = true;
		
		for (int i = 2; i <= N; i++)
		{
        	//2022년 1월 24일 지금 보니 이 부분에 if(array[i] == true) continue;를 추가해야 할것 같다.
			for(int k = 2; i*k <= N ; k++) 
			{
				array[i*k] = true;
			}
		}
		
		for (int i = M; i <= N ; i++)
		{
			if(array[i] == false) System.out.println(i);
		}

	}	
}

 

BufferedReader로 입력받기

입력에서 시간을 줄이는 방법으로 scanner 대신에 BufferedReader를 사용하는 방법이 있다고 해서 찾아봤다.

먼저, 제일 상단에 다음 코드를 추가한다. (방법1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

더 쉬운 방법도 있다. 아래처럼 *를 입력하면 io 디렉토리 안의 모든 클래스를 참조하겠다는 의미이다. (방법2)

import java.io.*;

이것도 귀찮다면, 필요한 함수들을 다 작성한 후에 최종적으로 ctrl+shift+O(이클립스)를 눌러주면 방법1의 코드들이 저절로 추가될 것이다. (방법3)

 

이제 원래 입력받던 자리에 다음 코드를 추가한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //Scanner scanner = new Scanner(System.in); 대신 사용
String input = br.readLine(); //여기부턴 int M = scanner.nextInt(); int N = scanner.nextInt(); 대신 사용하는 부분
StringTokenizer st = new StringTokenizer(input);
int M = Integer.parseInt(st.nextToken()); //정수로 형변환
int N = Integer.parseInt(st.nextToken());

 

입력받은 값을 저장할 때는 주의할 것이, readLine()을 이용하기 때문에 한줄 단위로 입력을 받는다는 것이다. 즉, Enter칠때까지 한줄을 String으로 입력받는다. 따라서 변수 input에 한줄의 내용을 모두 저장해준다. 이때 한줄에 정수 하나만 있는 경우에는 바로 정수형으로 형변환해주면 된다.

하지만 이번 백준을 풀기 위해선 공백을 기준으로 두 숫자를 구분할 필요가 있다. 이 땐 StringTokenizer를 통해 공백을 기준으로 토큰으로 분리하고, nextToken()을 이용해 하나씩 불러와 정수로 형변환해서 저장해주면 된다.

 

+참고로 한줄에 정수를 몇개 입력받는지 정해지지 않은 상황에선, hasMoreTokens() 함수를 통해 StringTokenizer에 토큰이 더 남아있는지 확인하는 방법을 사용할 수 있다. hasMoreTokens() 함수는 더 읽어들일 토큰이 있다면 True, 없으면 False를 반환하는 함수이다.

 

마지막으로, 다음과 같이 main함수 앞부분에 예외처리도 해줘야 한다. 왜 해줘야 하는지는 아직 공부 안했으니 생략

public static void main(String[] args) throws IOException {

 

BufferedReader를 이용해 입력받는 코드 전체는 다음과 같다.

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));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken()); //이 줄까지 변경되었다.
		
		final int SIZE = 1000001;
		boolean array[] = new boolean[SIZE];
		Arrays.fill(array, false);
		
		array[1] = true;
		
		for (int i = 2; i <= N; i++)
		{
		//2022년 1월 24일 지금 보니 이 부분에 if(array[i] == true) continue;를 추가해야 할것 같다.
			for(int k = 2; i*k <= N ; k++)
			{
				array[i*k] = true;
			}
		}
		
		for (int i = M; i <= N ; i++)
		{
			if(array[i] == false) System.out.println(i);
		}
        
	}
}

 

 

 

+

어디 얼마나 빨라지나 다시 제출해 봤는데 시간은 948 ->980.. 아직 나에겐 넘어야할 산이 많은 모양이다 ^ㅡ^

제일 상단에 있는게 수정된 버전이긴 한데...