试除法

$O(\sqrt{N})$

这道题的朴素做法是从1到N遍历一遍,时间复杂度是O(N)的,但是如果N的范围可以到10^9,就必须用更优的做法.
若$d >= \sqrt{N}$ 是N的约数,那么$N / d<=\sqrt{N}$也是N的约数.说明约数是成对出现的,d是N的约数,就有N/d是N的约数,我们只需要枚举$\sqrt{N}$ 以内的约数即可确定另一个约数,当然遇到平方数除外.

C++ 代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 100010;

int f[N], l = 0, r = N - 1;
int n;

int main(){
    scanf("%d", &n);
    int t = sqrt(n);
    for(int i = 1; i <= t; i++){
        if(n % i == 0){
            f[l++] = i;
            if(i != n / i) f[r--] = n / i;
            }
        }
    for(int i = 0; i < l; i++) printf("%d\n", f[i]);
    for(int i = r + 1; i < N; i++) printf("%d\n", f[i]);
    return 0;
}