프로그래머스 JAVA Level 1. 소수 찾기

카테고리 없음

러쉬허쉬 2023. 2. 11. 02:45

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

JAVA [자바] - 소수 구하는 알고리즘 및 구현

들어가기 전에 소수 [Prime Number] 소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다는 점은 누구나 알고 있을 것이다. 즉, 소수의 약수는 2개만을 갖고,

st-lab.tistory.com

단순히 Math.sqrt만 사용하니 시간초과를 피할 수 없었다.

그래서 검색하다가 에라토스테네스의 체라는 소수 판별 알고리즘에 대해 알게 되었다.

간단히 설명하면 k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시키는 방법이다.

즉, boolean 타입의 배열을 만들고, k=2면 2를 제외한 2의 배수를 모두 true로 만들어서

true인 경우 해당 숫자는 소수가 아니라고 판단하는 방식이다.

그럼 연산을 많이 생략 할 수 있어서 시간을 절약할 수 있다.

(1) boolean 타입의 배열을 선언하고, 크기는 n이하의 소수를 구할 경우 n+1로 선언한다.

boolean 타입의 배열의 인덱스 0, 1 은 소수가 아니니 미리 true로 바꾼다.

(2) 처음 2중 for문에서 boolean 타입의 배열이 true 경우 continue 하는 로직을 추가한다.

i는 2부터 시작하고, 구하고자 하는 숫자의 제곱근을 포함한 숫자까지 반복한다.

이때 i의 배수를 true로 바꾸는 로직을 추가한다.

(3) boolean 타입의 배열에서 false인 요소의 개수가 n이하의 소수의 개수다.