1929 - 소수구하기 (에라토스테네스의 체) java

 

기존에 소수를 구하는 방식으로 제출하면 시간초과가 뜬다.

에라토스테네스의 체가 뭔지 몰라서 검색해보았다.

2부터 자기자신을 제외한 배수들을  n까지 제외시키는 것이다. 이때 주의할 점은 이미 제외된 수는 넘어간다.

1은 소수기 때문에 따로 0으로 초기화했다.

 

 

package Exam;

import java.util.Scanner;

public class Exam1929 {
 //에라토스테네스의 체
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int num1 = sc.nextInt();
		int num2 = sc.nextInt();

		int [] a = new int[num2+1];

		for(int i=0; i<a.length; i++) {
			a[1] =0;
			a[i] =1;

		}

		for(int i=2; i<=num2; i++) {
			for(int j=2; i*j <=num2; j++) {
				a[i*j] =0;
			}
		}

		for(int i=num1; i<=num2; i++) {
			if(a[i] !=0) {
				System.out.printf("%d ", i);
			}
		}

	}

}