에라토스테네스의 체를 간단하게 알아보자.

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

 

 

1. 2는 소수입니다. 자기 자신을 제외한 2의 배수를 모두 지웁니다.
2. 3은 소수입니다. 3을 제외한 3의 배수를 모두 지웁니다.
3. 4는 2의 배수로, 소수가 아니므로 1번 과정에서 이미 지워졌습니다.
4. 5는 소수입니다. 5를 제외한 5의 배수를 모두 지웁니다.
5. 7은 소수입니다. 7을 제외한 7의 배수를 모두 지웁니다.
6. 이 과정을 x^2> n 이 될 때까지 반복합니다. 
7. 위의 그림의 경우 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워져도 충분합니다. 
8. 결국 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수입니다.

 

 

이 문제는 에라토스테네스의 체를 이용하여 소수를 구해내는 문제입니다.

 

구현 과정

에라토스테네스의 체

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

public class Main {
		public static void main(String[] args) {
			Scanner scan=new Scanner(System.in);

			int m=scan.nextInt();
			int n=scan.nextInt();
			boolean[] arr=new boolean[n+1];
			arr[0]=false;
			arr[1]=false;
			
			for(int i=2; i<=n; i++) {
				arr[i] = true;
			}
			
			for(int i=2; i<=Math.sqrt(n); i++) {
				for(int j=i; i*j<=n; j++) {
					arr[i*j]=false;
				}
			}
			
		for(int i=m; i<=n; i++) {
			if(arr[i]==true)
				System.out.println(i);
		}
		
	}
}

 

일반적인 구현 (제곱근 사용)

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);

		int a=scan.nextInt();
		int b=scan.nextInt();
		

		for(int i=a; i<=b; i++) {
            if(i<2)
                continue;
			boolean test=true;
			for(int j=2; j<=Math.sqrt(i); j++) {                     
				if(i%j==0) {
					test=false;
					break;
				}
			}
			if(test==true) {
				System.out.println(i) ;
			}
       }
		}
}