Jam's story
[프로그래머스] 소수찾기 본문
class Solution {
public int solution(int n) {
int answer = 1 , cnt=0;
for(int i=3; i<=n; i++){
for(int j=2; j<i; j++){
if(i%j==0) cnt++;
}
if(cnt==0){answer++;}
cnt=0;
}
return answer;
}
}
효율성 테스트 실패
에라토스테네스 체를 이용해야한다.
1. Math.sqrt로 제곱근을 찾아내어
2. 2부터 제곱근 사이에 잇는 배수를 모두 없애주면 된다.
3. 그 나머지는 다 소수이다.
class Solution {
public int solution(int n) {
int answer = 0;
boolean[] sosu=new boolean[n+1];
int root=(int)Math.sqrt(n);
for(int i=2; i<=n; i++){
sosu[i]=true;
}
for(int i=2; i<=root; i++){
if(sosu[i]==true){
for(int j=i; j*i<=n; j++){
sosu[i*j]=false;
}
}
}
for(int i=2; i<=n; i++){
if(sosu[i]==true)answer++;
}
return answer;
}
}//solution
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 약수의 합 (0) | 2022.08.06 |
---|---|
[프로그래머스] 시저 암호 (0) | 2022.08.05 |
[프로그래머스] 서울에서 김서방 찾기 (0) | 2022.08.04 |
[프로그래머스] 문자열 다루기 기본 (0) | 2022.08.03 |
[프로그래머스] 뉴스 클러스터링 (0) | 2022.07.28 |
Comments