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

 

 

 

https://ddamdoo.tistory.com/104

이 문제와 비슷한 문제이고, 인덱스만 달라졌다고 생각하고 아래와 같이 문제를 풀어보았다.

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

public class p1929 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		for (int i = a; i <= b; i++) {
			int cnt = 0;
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i % j == 0) {
					cnt++;
				}
			}
			if (cnt == 0) {
				sb.append(i + "\n");
			}
		}
		System.out.println(sb);
	}
}

 

하지만 시간초과가 났고, 이보다 효율적인 방법을 찾기 위해 검색해보다 아래 블로그에서 에라토스테네스의 체가 조금 더 효율적이라는 글을 보고 이를 구현하여 문제를 풀어보았다.

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

에라토스테네스의 체여도 크게 속도가 다를지에 대해서 고민했었는데, 만약 특정 숫자가 소수인 경우, 그 숫자의 배수들을 한번에 소수 불가 판정을 해주는 식으로 속도를 크게 줄일 수 있었다.

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

public class p1929 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		boolean[] prime = new boolean[b + 1];

		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;
			}
		}

		for (int i = a; i <= b; i++) {
			if(!prime[i]) {
				System.out.println(i);
			}
		}
	}
}