Java 소수찾기( prime number)

소수 : 1과 자신의 수 외에는 나눌 수 없는 숫자

1 ~ n (입력된 자연수) 사이의 소수 개수를 찾는 알고리즘, 찾아본 알고리즘 중에 가장 성능이 좋다.

import java.util.stream.IntStream;

public class SearchPrimeNumber {

    public int solution(int n) {

        int[] prime = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            prime[i] = i;
        }

        for (int i = 2; i <= n; i++) {
            if (prime[i] == 0) continue;
            for (int j = i; j <= n; j += i) {
                if (i != j && j % i == 0) prime[j] = 0;
            }
        }

        return (int) IntStream.of(prime).filter(i -> i != 0).count();
    }
}

You may also like...

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다