Algorithm/programmers_lv1
프로그래머스 lv1 소수 찾기 (Java)
EnvEng10
2023. 6. 16. 01:51
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/12921
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
| n | result |
| 10 | 4 |
| 5 | 3 |
풀이
class Solution {
public int solution(int n) {
int answer = 0;
boolean[] prime = new boolean[n + 1];
for (int i = 2; i <= n; i++){
prime[i] = true; //2 ~ n번째 수 초기화
}
int root = (int) Math.sqrt(n); //제곱근 구하기
for (int i = 2; i <= root; i++) { //2 ~ 루트n까지 검사
if (prime[i]) { //i번째의 수가 소수라면
for (int j = i; i * j <= n; j++) {
prime[i * j] = false; //해당 배수들을 모두 false로 초기화(배수는 소수x)
}
}
}
for (int i = 2; i <= n; i++) {
if (prime[i]) {
answer++;
}
}
return answer;
}
}에라토스테네스의 체를 사용한 풀이
반응형