소수-에라토스테네스

소수 / 에라토스테네스의 체

Summary

소수 판별은 n < 2를 먼저 처리한다.
에라토스테네스 반복문은 p++, 배수 제거는 q += p다.

---

소수의 특징

100 이하 소수의 개수: 25개
소수는 n > 3일 때 6k ± 1 형태만 가능하다.
단, 6k ± 1이라고 모두 소수는 아니다.

---

검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean[] isPrime = sieve(n);
 
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) count++;
        }
        System.out.println(count);
    }
 
    static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        if (n < 2) return isPrime;
 
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
 
        for (int p = 2; p <= n / p; p++) {
            if (!isPrime[p]) continue;
 
            for (int q = p * p; q <= n; q += p) {
                isPrime[q] = false;
            }
        }
 
        return isPrime;
    }
}

---

주의점

실수	주의
i++, q += i	반복 변수는 p, 배수 증가도 p
isPrime[1] 접근	n < 1이면 터짐. n < 2 먼저 처리
p * p <= n	overflow 가능. p <= n / p 권장
0, 1	소수 아님

---

백지 복원

1. 에라토스테네스에서 바깥 반복은 어디까지 도는가?
2. 안쪽 반복을 p * p부터 시작하는 이유는?
3. n = 0, 1일 때 어떻게 처리하는가?