hdu 1239Calling Extraterrestrial Intelligence Again

1743 ワード

問題は比較的に簡単で、書きやすくて、しかしテストのデータは多くて、TLにやさしいです......
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int pr[100001]={0};
int prime[50000];
int main()
{
	int m, a, b;
	int p, q, max, temp;
	int i, j, num=0;
	double d=sqrt(100000*1.0);
	for(i=2; i<=d; i++)//  
	    for(j=2; j*i<=100000; j++)
	    {
    		pr[i*j]=1;
    	}
	for(i=2; i<=100000; i++)
	{
		if(!pr[i])
		{
		   prime[num]=i;
		   num++;
		}
	}
	while( scanf("%d %d %d", &m, &a, &b) && (m||a||b) )
	{
		max=0;
		d=a*1.0/b;
		for(i=0; prime[i]<=m && i<num; i++);// ! ,  TL…… 
		i--;
		for(i; i>=0; i--)
		   for(j=i; j>=0; j--)
		   {
		   	  temp=prime[i]*prime[j];
   			  if(temp<=m && prime[j]*1.0/prime[i]>=d && temp>max)
		      {
      			max=temp; p=prime[j]; q=prime[i];
      		  }
    	   }
		printf("%d %d
", p, q); } }

牛のコードを添付して・・・
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100000
int n[MAX];
int main(int argc, char *argv[])
{
	int i, j, flag, m1, sq;
	int m, a, b;
	for(i=0; i<MAX; i++)
		n[i] = 1;
	n[0] = n[1] = 0;
	for(i=2; i<=(int) sqrt(MAX*1.0); i++)
		for(j=2; j*i <MAX; j++)
			n[i*j] = 0;  
	while(cin>>m>>a>>b, m||a||b)
	{

		m1 = m;
		flag = 0;
		while(m1)
		{
			sq = (int)sqrt((double)m1);
			while(sq >= 2)
			{
				if(n[sq] && m1%sq == 0 && n[m1/sq] && sq*1.0/(m1/sq) >=a*1.0/b)
				{
					cout<<sq<<' '<<m1/sq<<endl;
					flag = 1;
					break;
				}
				sq--;
			}
			if(flag) break;
			m1--;
		}
	}
	return 0;
}