CNUOJ 0486 800401反质数

难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

将正整数 x 的约数个数表示为 g(x)。例如，g(1)=1,g(4)=3, g(6)=4。 如果对于任意正整数y，当 0 < y < x 时，x 都满足 g(x) > g(y), 则称 x 为反质数。整数 1，2，4，6 等都是反质数。 现在任意给定两个正整数 M, N，其中，M < N <= 20000000，按从小到大输出其中（包括 M 和 N）的所有反质数。如果没有，则输出大写的NO。

输入

一行，包含两个正整数M和N，用单个空格隔开。

输出

在一行内输出所有反质数，以逗号间隔。如果没有，则输出 NO。

输入示例

1 13

输出示例

1,2,4,6,12

这题受到WXY的影响，立刻就做出来啦！哒哒哒

代码自己看，有注释，这在看不懂……就学学基础吧……相信大家都能看懂。

#include<iostream>//暴力做法，使用的WXY的做法，带了注释

using namespace std;

int n,m,t1,t2,i,j,k;//t1记录x约数 t2记录y的约数

bool flg=1,flr=1; //flg记录这个数是不是反质数，flr记录是不是第一个数，如果不是第一个要在前面补上逗号

int main()

{

    cin>>n>>m;

    for(i=n;i<=m;i++)

    {

        flg=1;//重置

        t1=0;//重置

        for(j=1;j<=i;j++) if(i%j==0) t1++;//寻找x所有约数

        for(j=1;j<i;j++)//y肯定小于x

        {

            t2=0;//重置

            for(k=1;k<=j;k++) if(j%k==0) t2++;//寻找y所有约数

            if(t2>=t1){flg=0;break;}//如果g(x)>g(y)，符合条件，退出，标记

        }

        if(flg && flr){cout<<i;flr=0;}//符合条件的第一个数

        else if(flg) cout<<','<<i;//符合条件的不是第一个数，前带逗号

    }

    return 0;

}

　　谢谢阅览！