#include <stdio.h>
#include <math.h>
int a[500000];
int b[200000];
int index_b=0;
int index;
void isp(int num)
{
	index=1;
	a[0]=5;
	for(int i=9;i<=num;i=i+4)
	{
		int j;
		for(j=0;j<index;j++)
		{
			if(i%a[j]==0)
				break;
		}
		if(j==index)
		{
			a[index++]=i;
		}
	}

}
bool isInA(int num)
{
	for(int i=0;i<index;i++)
	{
		if(num==a[i])
			return true;
	}
	return false;
}
void isHpr(int num)
{
	for(int i=0;i<index;i++)
	{
		if(num%a[i]==0&&num!=a[i]&&(num/a[i])%4==1)
		{
				b[index_b++]=num/a[i];
				break;
		}
	}
}
int  main()
{
	int aa;
	scanf("%d",&aa);
	while(aa!=0)
	{  
		isp(aa);
		index_b=0;
		int sum=0;
		for(int i=25;i<=aa;i=i+4)
		{	
			isHpr(i);
		}
		for(int j=0;j<index_b;j++)
		{
			if(isInA(b[j])==true)	
			{
				sum++;
			}
		}
		printf("%d %d\n",aa,sum);
		scanf("%d",&aa);
	}
	return 0;
}

• Re:高手指点,奇怪呀,为什么我的是O(N^2) 人家的也是这个,人家的都能过,怎么我的就会超时呢? (18) LeGendX 2008-06-05 10:00:59