C++로 특정 범위 내 소수 개수 구하기

두 개의 범위 변수 START와 END가 주어졌을 때, [START, END] 구간 안에 포함된 소수(Prime Number)의 개수를 구하는 것이 목표입니다.

소수 판별은 간단합니다. 숫자 i에 대해 1과 i/2 사이에 있는 어떤 수로도 나누어떨어지지 않는다면 그 수는 소수입니다. 이 조건을 만족할 때마다 카운트를 증가시키면 됩니다.

예제로 이해하기

입력

Start=1 End=20

출력

Primes in Ranges : 8

설명

1과 20 사이의 소수: 2, 3, 5, 7, 11, 13, 17, 19

입력

Start=100 End=200

출력

Primes in Ranges : 21

설명

100과 200 사이의 소수: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

알고리즘 접근 방식

• 범위 변수 START와 END를 입력받습니다.

• countPrimes(int strt, int end) 함수는 해당 범위 내 소수의 개수를 반환합니다.

• 카운트 변수 count를 0으로 초기화합니다.

• for 반복문을 사용해 i = strt부터 i <= end까지 순회합니다.

• 각 숫자 i에 대해 isprime(i) 함수를 호출하여 소수 여부를 검사합니다.

• isprime(int num) 함수는 소수가 아니면 0을, 소수이면 1을 반환합니다.

• 반복문이 끝나면 count를 결과값으로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int isprime(int num){
    if (num <= 1)
        return 0;
    for (int i = 2; i <= num/2; i++){
        if (num % i == 0)
            { return 0; }
    }
    return 1; // 두 조건 모두 통과하면 num은 소수
}
int countPrimes(int strt,int end){
    int count=0;
    for(int i=strt;i<=end;i++){
        if(isprime(i)==1)
            { count++; }
    }
    return count;
}
int main(){
    int START=10, END=20;
    cout <<endl<<"Primes in Ranges : "<<countPrimes(START,END);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Primes in Ranges : 4

10부터 20 사이에는 11, 13, 17, 19 총 4개의 소수가 존재합니다.

성능 최적화 팁

위 코드는 이해하기 쉽지만, 검사 범위를 i <= num/2 대신 i * i <= num, 즉 제곱근(√num)까지만 확인하도록 하면 시간 복잡도를 O(n)에서 O(√n)으로 크게 줄일 수 있습니다. 또한 범위가 매우 넓은 경우에는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하는 것이 훨씬 효율적입니다.