bool multi[100002];  // multi[i]表示i能被两个素数的乘积表示
int index[100002][2]; // 若multi[i] == 1 ，index[]存储对应的两个素数
int main()
{
    get_multi();

    while ( cin >> m >> a >> b && m != 0 )
    {
          t = m;
          find = 0;
          while ( !find )        //找符合要求的p，q
          {
                while ( !multi[t] ) t--;
                if (a * index[t][1] <= b * index[t][0]) // 因为t <= m , index[][0] <= index[][1]
                                                        // 故另外两个约束条件已满足
                   find = 1;
                else t--;
          }     

          cout << index[t][0] << ' ' << index[t][1] << endl;
    }
    
    return 0;
}

void get_multi()
{
     int prime[5200] ; //用筛法求50000以内的素数
      memset( multi , 0 , sizeof( multi ) );
     for ( i = 0 ; i < all ; i++ )
         for ( j = i ; j < all ; j++ )     
               if ( prime[i]*1.0*prime[j]*1.0 <= 100001 )  //大于这个范围的数不需要考虑
               {
                   temp_pq = prime[i] * prime[j];
                   multi[temp_pq] = 1;
                   index[temp_pq][0] = prime[i];
                   index[temp_pq][1] = prime[j];   // i <= j,保证了index[][0] <= index[][1]
               }
}

G++ 下用时110MS , C++ 157MS.
水平有限哈,多包涵.

• Re:一个思路 (1346) scut_bluewolf 2009-06-15 22:38:17