소수찾기 C++(에라토스테니스의 체)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀 더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기 | 프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

문제!!

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

 

 

제한사항

n은 2이상 1000000이하의 자연수입니다.

예시

n	return
10	4
5	3

 

입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

2. 문제풀이

---

1부터 n까지 소수의 개수를 찾는 문제입니다. 1부터 n까지 차근차근 소수인지 아닌지 판별을 하는방식도 있지만 소수를 찾는 과정은 비용이 비쌉니다. 더구나 시간도 오래걸리기 때문에 시간초과가 발생합니다. 따라서 일정범위 내에서의 개수를 찾으면 에라토스테니스의 체를 이용할 수 있습니다.   에라토스테니스의 체는 배수는 소수가 아님을 착안한 소수판별 알고리즘입니다. 소수를 찾으면 그 배수는 범위까지 소수가 아님을 체크하여 불필요한 연산을 배제하는 방식입니다. 예를 들어보겠습니다. 2를 계산하게 된다면 소수라고 판단합니다. 그렇다면 2의 배수는 전부다 소수가 아니라고 체크합니다. 3을 계산하게 된다면 소수라고 판단하고 3의 배수는 소수가 아니라고 체크합니다. 4를 계산하면 위에서 2의 배수는 소수가 아니라고 체크했기 때문에 넘어갑니다. 이렇게 N까지 계산하면서 소수일때마다 answer를 증가시키는 방식으로 문제를 풀면됩니다.

 

---

3. 소스코드

3.1 주석없는 코드

bool memo[1000000]{ false };
 
int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        if (memo[i - 1])        continue;
        answer++;
        for (int j = i + i; j <= n; j += i)        memo[j - 1] = true;
    }
    return answer;
}

3.2 주석있는 코드

bool memo[1000000]{ false };
/*
에라토스테니스의 체를 이용한 문제풀이
*/
 
int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        //어떤 수의 배수였다면 소수가 아니므로 패스
        if (memo[i - 1])        continue;
        //위의 조건을 건너왔다면 소수가 아니므로 카운트 증가
        answer++;
        //현재수의 배수부터 N까지 자신의 배수는 소수가 아닌것으로 변환
        for (int j = i + i; j <= n; j += i)        memo[j - 1] = true;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
 
using namespace std;
bool memo[1000000]{ false };
/*
에라토스테니스의 체를 이용한 문제풀이
*/
 
int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        //어떤 수의 배수였다면 소수가 아니므로 패스
        if (memo[i - 1])        continue;
        //위의 조건을 건너왔다면 소수가 아니므로 카운트 증가
        answer++;
        //현재수의 배수부터 N까지 자신의 배수는 소수가 아닌것으로 변환
        for (int j = i + i; j <= n; j += i)        memo[j - 1] = true;
    }
    return answer;
}
 
void print(int n, int answer) {
    int t = solution(n);
    if (answer == t)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print(10, 4);
    print(5, 3);
    return 0;
}

---

4. 결과