03. 에라토스테네스의 체

응용 백준 문제 : 1929

 

에라토스테네스의 체는 소수를 찾는 방법이다.

방법 : 2부터 시작해 소수들의 배의 수를 자신을 제외하고 제거해 나가며 소수를 찾는다.

 

@ 찾으려는 최대 구간과 크거나 가장 가까운 제곱수 의 자연수까지의 소수만 search하면 된다.

예를 들어, 1-120 구간 내의 소수를 찾는다고 하면 11의 제곱수는 121이므로 

에라토스테네스의 체를 이용하면 2부터 11까지의 소수를 찾아 계산하면 된다.

 

아래는 백준 1929를 에라토스테네스의 체를 이용해 푼 코드

import java.util.Scanner;

public class Main {
	
	static boolean [] array; //아무것도 넣지 않았을 때 모든 default는 false다
	static int M, N;

	public static void judgePrime()
	{
		//true : 소수 아님, false : 소수 맞음
		array[0] = true;
		array[1] = true;
		
		for (int i=2;i<=Math.sqrt(N);i++) 
		{
			if (array[i] == true) continue; //소수가 아니면 배수계산을 넘어간다.
			for (int j=(i*2);j<=N;j+=i)
			{
				array[j] = true;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		M = scanner.nextInt();
		N = scanner.nextInt();
		scanner.nextLine();
		
		array = new boolean[N+1];
		
		judgePrime();
		
		for (int i=M;i<=N;i++) {
			if (array[i] == false) System.out.println(i);
		}		
	}
}

+) 출력 성능이 좋지 않아

String Builder를 사용했다.

 

아래는 수정해서 stringBuilder를 사용한 코드

import java.util.Scanner;

public class Main {
	
	static boolean [] array; //아무것도 넣지 않았을 때 모든 default는 false다
	static int M, N;

	public static void judgePrime()
	{
		//true : 소수 아님, false : 소수 맞음
		array[0] = true;
		array[1] = true;
		
		for (int i=2;i<=Math.sqrt(N);i++) 
		{
			if (array[i] == true) continue; //소수가 아니면 배수계산을 넘어간다.
			for (int j=(i*2);j<=N;j+=i)
			{
				array[j] = true;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		M = scanner.nextInt();
		N = scanner.nextInt();
		scanner.nextLine();
		
		array = new boolean[N+1];
		
		judgePrime();
		
        //StringBuilder 사용
		StringBuilder stringbuilder = new StringBuilder();
		for (int i=M;i<=N;i++) {
			if (!array[i]) stringbuilder.append(i).append('\n');
		}
		System.out.println(stringbuilder);
	}
}