HDOJ 1239 Calling Extraterrestrial Intelligence Again

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目传送门： http://acm.hdu.edu.cn/showproblem.php?pid=1239

搜索的题目。我感觉这题直接判断是否满足条件就OK了，为何HDOJ的课件上还说用剪枝？谁能告诉我？先分析：得到：2<= p,q <=10000。再用筛选法打表求出10000以内的素数，接着就是搜索遍历了。

#include 
using namespace std;
__int64 m, a, b, p, q;
__int64 _maxa, _maxb, _max;

bool vis[10001];
int prime[5000];
int main()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 2; i <= 100; i++)
        for(int j = i*2; j <= 10000; j += i)
            vis[j] = 1;
    int n=0;
    for(int i=2; i<=10000; ++i)
        if(vis[i] == 0)
            prime[n++] = i;
    bool flag=0;
    while(scanf("%I64d %I64d %I64d", &m;, &a;, &b;) && (a+b+m))
    {
        _max = _maxa = _maxb = 0;
        flag = 0;
        for(int i=n-1; i>=0; --i)
        {
            for(int j=n-1; j>=i; --j)
                if((prime[j]*prime[i] <= m) && (prime[j]*prime[i]>_max) && (double)prime[i]/prime[j]>=((double)a/b))
                {
                    _max = prime[j]*prime[i];
                    _maxa = i;
                    _maxb = j;
                }
        }
        printf("%d %d\n", prime[_maxa], prime[_maxb]);
    }
    return 0;
}