에라토스테네스 체 (소수찾기)

 

 

1. 초기화:
   • 2부터 원하는 범위 nnn까지의 모든 정수를 나열합니다.
   • 소수를 판별하기 위해 각 숫자에 대해 "소수인지 아닌지"를 기록할 배열을 생성합니다. (예: true/false로 초기화)
2. 2부터 시작:
   • 첫 번째 소수인 2를 선택합니다.
   • 2의 배수들을 모두 제거합니다(2는 제외). 즉, 4, 6, 8, ... 등을 지웁니다.
3. 다음 숫자로 이동:
   • 다음 남아있는 숫자를 찾습니다(소수임).
   • 그 숫자의 배수를 모두 제거합니다.

    public static List<Integer> findPrimes(int n) {
        // 소수 여부를 표시하는 배열 생성
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        // 2부터 시작해서 각 숫자의 배수를 제거
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) isPrime[j] = false;
            }
        }
        // 소수만 리스트에 추가
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes.add(i);
        }
        return primes;
    }