class2 - 1929번 소수 찾기 (자바)

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

해당문제는 변수는 1000000까지 될 수 있으나 제한 시간이 2초여서 알고리즘을 사용해야한다.

 

문제 풀 때 필요한 개념

에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.

임의의 수 N 까지의 소수를 구하고자 할 때,

2부터 √N (제곱근) 까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다.

2 * 4 = 4 * 2 처럼 모든 약수를 구하기에는 겹치는 부분이 많아 비효율적이다.

그래서 주어진 수의 제곱근 까지만 약수를 구하면 효율적으로 소수를 구할 수 있다.

 

1. 2부터 √N 까지의 배수를 제외시킨다.

2. 배수를 구할 때는 자기 자신을 뺀다.

3. 제외된 수는 배수를 구하지 않고 넘어간다.

 

풀이

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

public class Main {
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            Boolean[] arr = new Boolean[end+1];
            
            Arrays.fill(arr, true); // 초기값 세팅
            arr[0] = false; // 0은 무조건 false로 세팅한다.
            arr[1] = false; // 1은 무조건 false로 세팅한다.
            int real_end = (int)Math.sqrt((double)end); 
            
            for (int i = 2; i <= real_end; i++) {	
                if (!arr[i]) continue;
            	for (int j = 2; i*j <= end; j++) {
            	    arr[i*j] = false;
            	}
            }
            
            
            // 출력
            for (int i = start; i <= end; i++) {
                if (arr[i]) {
                    bw.write(String.valueOf(i)+"\n");
                }
            }
           

            // close
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}	
	}
}

 

 

문제푼 과정

package backjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class q_1929 {
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            List<Integer> results = new ArrayList<>();
            
            for (int i = start; i < end; i++) {	
            	for (int j = 2; j < 1000000; j++) {
            		if (i == 2 || i == j) {
            			results.add(i);
            			break;
            		}
            		else if (i == 1 || i % j == 0) {
            			break;
            		}
            	}
            }
            
            
            // 출력
            for (Integer result : results) {
            	 bw.write(String.valueOf(result)+"\n");
            }
           

            // close
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}	
	}
}

이렇게 했더니 시간초과가 나서 다른 방법을 찾아보게 되었고,

이 문제는 알고리즘을 이용해서 풀어야 되는 문제임을 알게되었다.