728x90
프로그래머스 1단계
소수 찾기
https://programmers.co.kr/learn/challenges
문제 설명
풀이
class Solution {
public int solution(int n) {
/* 에라토스테네스의 체 알고리즘을 이용해야 효율성이 높아짐 */
int answer = 0;
boolean [] arr = new boolean[n+1]; //arr값이 true이면 해당 값은 소수이다.
arr[0] = arr[1] = false; //0과 1은 소수가 아님으로 간주한다.
for(int i=2; i<=n; i++) { //2부터 범위 끝까지 우선 소수(true)로 설정한다.
arr[i] = true;
}
for(int i=2; i*i<=n; i++) { // i의 배수들은 소수가 아니므로 제외(false)시킨다
for(int j=i*i; j<=n; j+=i) {
arr[j] = false;
}
}
for(int i=0; i<=n; i++) { //true인 값들은 소수이므로 answer에 1씩 카운트한다
if(arr[i] == true) {
answer++;
}
}
return answer;
}
}
728x90
'알고리즘 > 프로그래머스 1단계' 카테고리의 다른 글
[프로그래머스] 약수의 합 (0) | 2022.04.23 |
---|---|
[프로그래머스] 문자열을 정수로 바꾸기 (1) | 2022.04.23 |
[프로그래머스] 문자열 다루기 기본 (0) | 2022.04.23 |
[프로그래머스] 문자열 내 p와 y의 개수 (1) | 2022.04.23 |
[프로그래머스] 두 정수 사이의 합 (1) | 2022.04.23 |
댓글