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(); } }
최신 댓글