[백준/C++] 1978번: 소수찾기- 제곱근을 이용한 최적화

1. 문제 정보

• 문제 번호: 1978번
• 문제 이름: 소수 찾기
• 사용 언어: C++
• 문제 링크: 백준 1978번 바로가기
• 문제 요약:(소수는 1과 자기 자신으로만 나누어떨어지는 수이며, 1은 소수가 아니다.)
• 주어진 N개의 수 중에서 소수(Prime Number)가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

2. 접근 방법 (알고리즘)

소수를 판별하는 가장 기본적인 방법은 2부터 자기 자신 직전(N-1)까지 나누어보는 것이다.

처음 작성한 코드 

#include <iostream>
#include <vector>
using namespace std;
int main() {
   int n;
    cin>>n;
    vector<int> list; //벡터로 list 받기
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value; 
        list.push_back(value); 
    }

    int count=0;
    for(int j=0;j<n;j++){
        int number=list[j];
        if(number<=1){ //해당 자연수가 1일 때 넘기기
            continue;
        }
        bool check=false;
        for(int i=2;i<number;i++){
            if(number%i==0){
                check=true;
                break;
            }
        
    }
        if(!check){
            count++;
        }
    }

    cout<<count;
    
    
}

 

 

 

 

(하지만 숫자가 커지면 이 방법은 시간이 오래 걸린다.)

해결 개념: 제곱근까지만 검사하기

약수들은 대칭성을 가진다.

36을 예로 들면,

 

가운데 6 X 6을 기준으로 약수들이 대칭을 이룬다.

즉, 제곱근 N 까지만 나누어떨어지는지 확인하면, 그 뒤는 굳이 검사할 필요가 없다.

 

최적화된 코드

for(int i = 2; i * i <= number; i++){  //제곱근까지만
    if(number % i == 0){
        isNotPrime = true;
        break;
    }
}

 

4. 배운 점 & 회고 (TIL)

A. 소수 판별의 시간 복잡도 (O(N) vs O(sqrt(N))

• 전체 검사 (O(N)): $N$이 10억이면 10억 번 연산해야 한다. 시간 초과가 날 가능성이 높다.
• 제곱근 검사 (O(sqrt{N})): N이 10억이어도 약 3만 번만 연산하면 된다.
• 결론: 소수 판별 문제에서 시간 제한을 넘기지 않으려면 "제곱근 최적화"를 습관화해야 한다.
  
  

B. 예외 처리 (1은 소수가 아니다)

이 처리를 안 해서 틀리는 경우가 많다. 1은 소수도 합성수도 아니므로 반드시 로직 맨 처음에 제외해야 한다.

 

C. std::vector 사용법과 동적 배열

기존 배열(int arr[100])은 크기를 미리 정해야 해서 불편했는데, 이번에 std::vector를 처음 사용해 봤다.

• 유동적인 크기: push_back()을 사용하면 데이터가 들어오는 만큼 자동으로 크기가 늘어난다. 입력 개수(N)가 정해지지 않았거나 변할 때 매우 유용하다.
• 편리한 관리: 배열의 길이를 따로 변수로 관리할 필요 없이 .size() 함수로 알 수 있다.

---

💡 멘토의 팁: i * i <= number를 쓰는 이유

왜 i <= sqrt(number)라고 안 쓰고 i * i <= number라고 쓸까요?

1. 속도: sqrt() 함수를 호출하는 것보다 단순 곱셈(*)이 훨씬 빠릅니다.
2. 정확도: sqrt()는 실수(float/double)를 반환하기 때문에 아주 미세한 부동 소수점 오차가 발생할 수 있습니다. 정수론 문제에서는 정수 연산만 사용하는 것이 가장 안전합니다.

---

 

📚 [부록] std::vector 핵심 개념 정리

 

 

Vector(벡터)는 C++ 표준 라이브러리(STL)에 있는 '크기가 변하는 배열(Dynamic Array)'이다.
알고리즘 문제 풀이의 필수품!

 

 

1. 선언 및 초기화

#include <vector> // 필수 헤더

vector<int> v;             // 비어있는 벡터 생성
vector<int> v(5);          // 0으로 초기화된 5개짜리 벡터 생성 [0,0,0,0,0]
vector<int> v(5, 2);       // 2로 초기화된 5개짜리 벡터 생성 [2,2,2,2,2]

 

 

2. 데이터 삽입

v.push_back(10); // 맨 뒤에 10 추가
v.push_back(20); // 맨 뒤에 20 추가

 

3. 데이터 접근 (배열과 동일)

cout << v[0]; // 첫 번째 원소 출력
cout << v.at(0); // v[0]과 같지만, 범위를 벗어나면 에러를 띄워줌 (더 안전함)

 

 

4. 자주 쓰는 함수

• v.size(): 현재 벡터에 들어있는 원소의 개수 반환
• v.pop_back(): 맨 뒤의 원소 삭제
• v.clear(): 모든 원소 삭제 (크기가 0이 됨)
• v.empty(): 비어있으면 true, 아니면 false 반환