소수를 효율적으로 구해보자

https://school.programmers.co.kr/learn/courses/30/lessons/136798

이 문제를 푸다 느낀 것들을 이야기해보려고 함.
처음에 문제를 풀 때 소수의 개수를 구하는 부분에서 코드를 어떻게 짰냐면

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    
    
    int answer = 0;
    int count;
    vector<int> weapon_list;
    
    // 소수 구하는부분
    for(int i=1;i<=number;i++){
        count = 0;
        for(int j=1;j<=i;j++){
            if(i%j==0) count++;
        }
        weapon_list.push_back(count);
    }
   
    for(int i=0;i<weapon_list.size();i++){
        if(weapon_list[i] > limit) answer += power;
        else answer += weapon_list[i];
    }
    return answer;
}

결과는?

시간 초과..

처음 문제에 대해 생각할 땐
1. 2중 for문이 문제인가?
-> 이건 아닐것 같았는게, 1~number 사이 수의 약수의 개수를 전부 구해야했기에 2중for문은 필요했었다고 생각

2. 약수의 개수를 구하는 구현부분에서 무언가 쓸데없이 시간낭비하는 부분이 있나?
   -> 이게 정답이였음

어떻게 바꿔야 할까?

소수를 구하는 방식을 머리 속으로 생각해 봤음.

12의 약수를 구할 때 저 위에 있는 for문대로 생각해보면
12 % 1 > 0
12 % 2 >0
12 % 3 > 0
....
12 % 12 > 0

1부터 12까지 전부 돌아서 약수의 개수를 확인한다.
가장 정확한 방법이라고 말할 수 있겠으나, 만약 number의 수가 문제 제한 범위인 100,000이라면? 굉장히 오래걸린다 할 수 있다.

소수의 개수를 구할 때 만약 12를 구한다 하면
1x12 / 2x6 / 3x4 => 6개 이런식으로 구했다.
머리속에 for문을 구현해보면, 우리는 1~3까지 밖에 안 돌았는데도 벌써 12의 약수를 전부 구해버린 모습이다.
그럼 어디까지 돌아야하는지 for문의 범위를 정의해주는 것이 문제인데...

그 범위를 수의 제곱근으로 설정해주는 것이 일반적인 최적화 방법이다.

#include <string>
#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    
    
    int answer = 0;
    int count;
    vector<int> weapon_list;
    
    for(int i=1;i<=number;i++){
        count = 0;
        // 소수 구하는 부분
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                if(j!=(i/j)) count += 2;
                else count += 1;
            }
        }
        weapon_list.push_back(count);
    }
    
    for(int i=0;i<weapon_list.size();i++){
        if(weapon_list[i] > limit) answer += power;
        else answer += weapon_list[i];
    }
    return answer;
}

시간복잡도를 제곱근 만큼 줄일 수 있다.