반응형
-첫 풀이
class Solution {
public int solution(int n) {
int answer = 0;
for(int i = 2; i<=n;i++){
int temp = 0;
answer++;
for(int j=1;j<i;j++){
if(temp>1) {
answer--;
break;
}else if(i%j == 0) {
temp++;
}
}
}
return answer;
}
}프로그래머스 level 1로 분류되어 있는 소수 찾기 문제이다. 처음의 생각은 반복문을 통해 2부터 n까지의 정수들을 1부터 자신 전까지 나눈 나머지가 2개 이상인 경우, 소수가 아니라고 판단하는 식으로 진행했다. 이 경우 데이터의 범위가 1,000,000이기 때문에 뒤에 나오는 테스트 케이스에서 시간 초과 및 효율성 체크에서 좋지 않은 결과를 가져왔다.
- 에라토스테네스의 체 알고리즘
인터넷의 도움을 받아 소수를 판별하는 알고리즘인 '에라토스테네스의 체'에 대해서 처음 접하게 되었다. 알고리즘의 핵심 내용은 2부터 시작해(1은 소수가 아니므로) 자기 자신을 제외한 배수들을 모두 '체'에 걸러주면 된다.
1. '체'로 거르기 위한 1차운 배열을 생성한다. (n+1 크기)
2. 2부터 배수들을 모두 체크해준다. (단, 자신은 제외하고 4,6,8,10..... <= n)
3. 다음 3의 배수들을 모두 체크해준다.
4. 4는 앞선 2의 배수로써 체크가 되어 소수가 아니기 때문에 넘어간다.
이와 같은 방식으로 진행하면 결국 2,3,5,7,11 등 소수들의 배수들이 모두 걸러지게 되며 소수들만 남게 된다.
class Solution {
public int solution(int n) {
int answer = 0;
// 1. 에라토스테네스의 체로 거르기 위한 1차원 배열.
boolean check[] = new boolean[n+1];
// 2. 2부터 n까지의 수들 중
for(int i =2;i<=n;i++){
// 2-1. 소수의 배수로써 걸러진 수들은 넘어가고, (4,6,8,9..... 등)
if(check[i] == true) continue;
// 2-2. 자신을 제외한 배수를 고려하기 위해 i+i; j<=n;j=j+i 조건으로 걸러준다.
for(int j=i + i;j<=n;j+=i){
check[j] = true;
}
}
// 3. 걸러지지 않은 수 들의 개수를 카운팅.
for(int i=2;i<=n;i++){
if(!check[i]) {
answer++;
}
}
return answer;
}
}에라토스테네스의 체 알고리즘은 넓은 범위의 데이터들 가운데 소수를 판별하는데 효과적인 알고리즘이지만, 특정 수가 소수인지 판별하는 경우는 비효율적이라고 한다.
반응형