프로그래머스 코딩테스트연습 소수 찾기
자꾸 효율성 테스트에서 실패하여서 살짝 힌트를 봤다.
그랬더니 어떠한 소수의 제곱근 이하의 소수로 나누었을 때 나누어지지 않는다면 소수다.
라는 힌트를 받았다.
71로 제곱근을 계산해보면 8*8 ~ 9*9 사이니 8.xxxx가 나올 것이다.
8 이하의 소수는 2 3 5 7이 있다.
해당 4개의 소수로도 안 나누어진다면 그 숫자는 소수인 것이다.
class Solution {
public int solution(int n) {
int count = 0;
for(int i = 2; i < n+1; i++){
if(i % 2 == 0 && i != 2) continue;
boolean ableDiv = false;
for(int j = 2; j <= Math.sqrt(i); j++){
if(i % j == 0){
ableDiv = true;
break;
}
}
if(!ableDiv) count++;
}
return count;
}
}
설명
- count : 소수의 갯수
- i : 자연수
- j : 제곱근 이하의 숫자만큼 반복
- ableDiv : 나눌 수 있는가 여부
if(i % j == 0){
ableDiv = true;
break;
}
- 제곱근 이하의 숫자 j를 돌면서 자연수를 j로 나누었을 때 나머지가 0 ( 나누어 떨어진다 ) 이라면
ableDiv = true, 그 즉시 반복문 탈출
if(i % j == 0){
ableDiv = true;
break;
}
ableDiv = true, 그 즉시 반복문 탈출
반복을 다 돌아도 나누어 떨어지는 숫자가 없다면 해당 숫자는 소수이므로 count++
Author And Source
이 문제에 관하여(프로그래머스 코딩테스트연습 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yskim9718/프로그래머스-코딩테스트연습-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)