소수 구하기 - JAVA

1. 루트n 까지만 확인하기

for(int i=2; i<=n; i++) {
    // j*j<=i는 j<=루트i에서 양쪽을 제곱한 결과다
    for(int j=2; j*j<=i; j++) {
        count++;
        if(i%j == 0) {
            key = 1;
            break;
        }
    }
    if(key == 0) {
        sb.append(i).append('\n');
    }
}

n이 아니라 루트n까지만 확인하는 이유는
16 = 1 x 16
2 x 8
4 x 4
8 x 2
16 x 1
에서 4 x 4를 기점으로 같은 수가 반복된다.
그래서 루트 n까지만 확인해도 소수를 다 알 수 있다.

2. 합성수를 모두 체크하기

private void find_decimals() {
    for(int i=2; i*i<isComposition.length; i++){
        //합성수면 돌아가기
        if(isComposition[i]) continue;
        //합성수 true로 표시하기
        for(int j=i*i; j<isComposition.length; j+=i){
            isComposition[j] = true;
        }
    }
}

2의 배수를 다 체크했기 때문에 2의 배수인 4, 6, 8, 10 등의 수의 배수를 다시 확인할 필요가 없다.
따라서 true표시된 수의 배수는 확인할 필요가 없다
그래서 if(isComposition[i])로 확인하고 합성수인 경우 continue로 다음 수로 넘어갔다.