[algorithm 풀이] 2. 소수의 개수

0. 문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.

1. 입력설명
   • 첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
2. 출력 설명
   • 첫 줄에 소수의 개수를 출력합니다.
3. 입력 예제1
   • 20
4. 출력 예제1
   • 8
5. 문제 풀이 핵심
   • 소수를 구할 때 n까지 할 필요 없고 sqrt(n)까지만 하면 된다.!

1. 풀이1 : 소수를 별도 컨테이너에 저장하여 비교

1. 사용자에게 num을 입력 받음
2. 소수를 관리할 컨테이너 생성 및 2를 추가
3. i 는 3~num 까지 순회
   • j는 소수 컨테이너를 순회
   • i를 j번째 소수로 나누어 나머지가 0 이면 바로 멈춤
   • j가 소수 컨테이너를 다 순회하였으면, i를 소수 컨테이너에 추가
4. 소수 컨테이너 사이즈를 출력

#include<iostream>
#include<vector>
int main() {
    int num, i, j;
    std::cin >> num;
    std::vector<int> sosus;
    sosus.push_back(2);
    for (i = 3; i <= num; i++) {
        for (j = 0; j < sosus.size(); j++) {
            if (i % sosus[j] == 0) {
                break;
            }
        }
        if (j == sosus.size()) {
            sosus.push_back(i);
        }
    }

    std::cout << sosus.size();
    return 0;
}

5. 예제(20 입력 시)
   • 3 => 1번 순회 {2,3}
   • 4 => 2번 순회 {2,3}
   • 5 => 2번 순회 {2,3,5}
   • 6 => 3번 순회 {2,3,5}
   • 7 => 3번 순회 {2,3,5,7}
   • 8 => 4번 순회 {2,3,5,7}
   • 9 => 4번 순회 {2,3,5,7}
   • 10 => 4번 순회 {2,3,5,7}
   • 11 => 4번 순회 {2,3,5,7,11}
   • 12 => 5번 순회 {2,3,5,7,11}
   • 13 => 5번 순회 {2,3,5,7,11,13}
   • 14 => 6번 순회 {2,3,5,7,11,13}
   • 15 => 6번 순회 {2,3,5,7,11,13}
   • 16 => 6번 순회 {2,3,5,7,11,13}
   • 17 => 6번 순회 {2,3,5,7,11,13,17}
   • 18 => 7번 순회 {2,3,5,7,11,13,17}
   • 19 => 7번 순회 {2,3,5,7,11,13,17,19}
   • 20 => 8번 순회 {2,3,5,7,11,13,17,19}
   • 총 : 83번 순회

2. 풀이2 : i의 제곱근까지만 순회

1. 사용자에게 num을 입력 받음
2. i 는 2~num 까지 순회
   • j는 2 부터 i의 제곱근 까지 순회
   • i 를 j로 나누어 떨어지면 break
   • j가 끝까지 순회했으면 개수를 +1
3. 개수 출력

#include<iostream>

int main() {
    int num, i, j, cnt = 0;
    bool flag;
    std::cin >> num;
    for (i = 2; i <= num; i++) {
        flag = true;
        for (j = 2; j * j <= i; j++) {
            if (i%j == 0) {
                flag = false;
                break;
            }
        }
        if (flag == true) cnt++;
    }
    std::cout << cnt;

    return 0;
}

4. 예시(20 입력시)
   • 2 => 1회 순회(j=2)
   • 3 => 1회 순회(j=2)
   • 4 => 1회 순회(j=2)
   • 5 => 1회 순회(j=2)
   • 6 => 1회 순회(j=2)
   • 7 => 1회 순회(j=2)
   • 8 => 1회 순회(j=2)
   • 9 => 2회 순회(j=2,3)
   • 10 => 2회 순회(j=2,3)
   • 11 => 2회 순회(j=2,3)
   • 12 => 2회 순회(j=2,3)
   • 13 => 2회 순회(j=2,3)
   • 14 => 2회 순회(j=2,3)
   • 15 => 2회 순회(j=2,3)
   • 16 => 3회 순회(j=2,3,4)
   • 17 => 3회 순회(j=2,3,4)
   • 18 => 3회 순회(j=2,3,4)
   • 19 => 3회 순회(j=2,3,4)
   • 20 => 3회 순회(j=2,3,4)
   • 총 36회 순회
5. 풀이1 vs 풀이2
   • 풀이 1 : 83번 순회로 계산 가능
   • 풀이 2 : 36번 순회로 계산 가능
   • 풀이 2가 훨씬 효율적

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비