약수 출력하기

문제는 여기 참조

 

브루트포스 $O(N)$

for (int i = 1; i <= n; i++) {
    if (n%i == 0) {
        printf("%d ", i);
    }
}
 

 

$O(\sqrt{N})$

set<int> s;
for (int i = 1; i*i <= n; i++) {
    if (n%i == 0) {
        s.insert(i);
        s.insert(n / i); // 10%2를 생각해보면 2와 5가 약수이니까 한번에 처리해주는것
                         // set으로 처리하는 이유는 4%2를 생각해보면 2가 두번 들어갈 수 있음
    }
}
for (auto e : s) {
    printf("%d ", e);
}
 

 

특정 수 하나의 약수를 구하는게 아니라, 여러수의 약수를 동시에 구할때는 에라토스테네스의 채처럼 접근해야 복잡도가 훨씬 작아짐을 발견했다. 이 문제를 풀면서 발견할 수 있었고, 아래 코드는 해당 문제의 답변이기도 하다.

#define IN(n) int n;cin>>n
#define OUT(x) cout << (x) << endl
 
int32_t main(){
    const int MAX = 1000000;
    vector<int> f(MAX+1,0);
    for (int i = 1; i <= MAX; i++) {  // i를 약수로 가지는 애들은 모두 찾겠다!
        for (int j = 1; i * j <= MAX; j++)  // 범위내 i의 배수를 모두 구해서
            f[i * j] += i;  // i를 다 더해줌
    }
    vector<ll> g(MAX+1,0);
    for (int i = 1; i <= MAX; i++) {
        g[i] = g[i-1] + f[i];
    }
    IN(T); while (T--) {
        IN(N); OUT(g[N]);
    }
    return 0;
}