最新消息:

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

C++ 少儿编程 1785浏览 0评论
2019年海淀区青少年程序设计题解

1

约数

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

#include <iostream>

using namespace std;

int main(){

    int n;

    cin >> n;

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

        if(% 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;<=sqrt(n);i++){

        if(% i == 0){

            cout << n/<< endl;

            return 0;

        }

    }

    cout << << endl;

    return 0;

}

转自公众号:
noip案例讲解

您必须 登录 才能发表评论!