[수학] 백준 - 소수 구하기

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

1929번: 소수 구하기

 

-문제해설

일반적으로 그냥 반복문돌려서 소수를 찾으려고하면 O(n)의 시간복잡도로 시간초과가 나버린다. 따라서 이보다 시간을 줄일 수 있는 코드가 필요하다.

 

이때 이용하는 알고리즘이 '에라토스테네스의 체'이다. 

간단히 설명하자면 만약 2가 나왔을 때 2를 제외한 2의 배수들은 모두 제거하는 식이다.

2 3 4 5 6 7 8 9 10 11 12 13 14 15가 있을 때 2배수 제거

2 3 5 7 9 11 13 15  다음으로 3의 배수 제거

2 3 5 7 11 13  다음으로 5의 배수 제거

2 3 5 7 11 13  다음으로 7의 배수 제거 ....

 

이런식으로 한 다음에 m과 n 사이에 있는 소수들만 모두 출력하면 된다.

 

 

-자바

package math;

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

public class BJ1929 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		
		StringBuffer sb = new StringBuffer();
		int[] sosu = new int[m+1];
		
		for( int i=2; i<=m; i++ ) {
			if( sosu[i] == 1 ) continue;
			
			for( int j=i*2; j<=m; j+=i ) sosu[j] = 1;
			
			if( i >= n && i <= m ) sb.append( i+"\n" );
		}
		System.out.println( sb );
	}
}

 

-파이썬

import sys

def sosu( i, m, n, arr ):
    if arr[i] == 1: return False
    for j in range( i+i, n+1, i ): arr[j] = 1
    if i >= m and i <= n: return True

m, n = map(int, sys.stdin.readline().split() )
arr = [0] * (n+1)
print( "".join( str(i)+"\n" if sosu( i, m, n, arr ) else "" for i in range( 2, n+1 ) ) )