자바 소수 구하기

소수 구하기

소수는 자신과 1외의 정수로 나누어 떨어지지 않는 정수

1000 미만의 정수 중 소수 구하기

public static void main(String[] args){
	for(int n = 2; n < 1000; n++){
    	int i;
        for(i=2; i<n; i++){
        	if(n%i==0) // 나누어 떨어지면 소수가 아님
            	break; 
        }
        if(n==i)
        	System.out.print(n);
    }
}

업그레이드 버전

에라토스테네스의 체를 사용해서 더 빠르게 계산하기

에라토스테네스의 체

소수가 되는 수의 배수를 지우면 남은 건 소수가 된다

소수가 무엇인지 찾을 필요가 없으며 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.
또한 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근까지만 소수인지 아닌지를 확인하면 된다.

정해진 숫자 a부터 b까지의 소수를 모두 구해라

static void primeNumber(int m, int n) {
        int[] arr = new int[n+1];
        StringBuilder sb = new StringBuilder();
        
        //배열 초기화
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
        
        //2부터 시작해서 i의 배수들을 배열에서 지워준다
        for (int i = 2; i <= n; i++) {
            //이미 지워진 수는 건너뛴다
            if (arr[i] == 0) continue;  
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }
        for (int i = m; i <= n; i++) {
            if (arr[i] != 0) sb.append(i + "\n");
        }
        System.out.print(sb);
    }