2019年海淀区青少年程序设计挑战活动复赛小学组C++试题第1题题解

1

约数

    分析：从n-1到1，从大到小，一个一个试除取余，看能否整除，如果可以整除，则输出这个数并结束整个程序。时间复杂度为O(N)。数据n的范围2*10⁹，代码如下，但可以简化循环的次数来优化。

#include <iostream>

using namespace std;

int main(){

    int n;

    cin >> n;

    for(int i = n-1;i >= 1;i–){

        if(n % i == 0){

            cout << i << endl;

            break;

        }

    }

    return 0;

}

    改进：约数即为能整除的数，n/d=m；d*m = n；假设d为最大约数，那么m一定为最小约数。当d与m无限接近的时候，也就是m为最小约数中的最大值。所以m的最大值为n的开方。这样我们可以去求m，最小约数m求出来后，最大约数d = n/m。而m的判断范围从2到n的开方。循环次数大大缩小。

#include <iostream>

#include <cmath>

using namespace std;

int main(){

    int n;

    cin >> n;

    for(int i = 2;i <=sqrt(n);i++){

        if(n % i == 0){

            cout << n/i << endl;

            return 0;

        }

    }

    cout << 1 << endl;

    return 0;

}

转自公众号：
noip案例讲解