에라토스테네스의 체

소수 구하는 알고리즘

처음엔 for과 % 를 이용해서 나머지값이 1과 자신인값만 있는 숫자들을 출력하는 방식으로 제출했으나

시간초과뜸

BufferedReader, writer 쓰고 별짓을 해도 계속 시간초과.

 

알아보니 for로 모든숫자를 돌아가면서 나머지값 두개인녀석 찾는거 너무 비효율적이었음.

여기서 시간복잡도라는 개념을 알게됨>> 아직 정확하게는 모르는데 공부할예정

 

에라토스테네스의 체를 이용하면 된다는 이야기를 들음

정리해보면 에라토스테네스의 체를 이용하여 미리 소수표를 만들어놓고,

그냥 조건에 해당하는 숫자들만 출력하는 느낌

 

에라토스테네스의 체는

쉽게말해 배수제거

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

....

이렇게 숫자가 있으면

 

소수는 2357 이런식으로

1과 자기자신만을 약수로 갖는 숫자이기때문에

예를들어 2의 배수인 4 6 8 10 얘네들은 약수 중 2를 반드시 포함하기때문에 그러면

 1 ,2 , ..., 자기자신

최소 3개가 되기때문에 소수가 될수 없는 것처럼

어떤수의 배수들을 다 제거하면 된다는말

대신 그 '어떤수'는 그대로 두면되고 그게 소수가 될것임.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a= sc.nextInt();
		int b= sc.nextInt();
		int num=1000000;
		
		int[] arr= new int[num+1];
		
		for(int i =2 ; i<=num;i++) {
			arr[i]=i;
		}
		for(int i=2;i<num;i++) {
			if(arr[i]==0)continue;
			for(int j=i+i;j<=num;) {
				arr[j]=0;
				j=j+i;
			}
		}
		for(int i=0;i<num;i++) {
			if(arr[i]==0)continue;
			if(arr[i]>=a && arr[i]<=b) {
				System.out.println(arr[i]);
			}

		}
	
	}

}