10366 Problem A 完全平方数

问题 A: 完全平方数

题目描述

在四位自然数中有这样一些特点的数：
(1)它们是素数；
(2)将这些素数加上45后得到一个新的数值；
(3)请同学们在这些新的数值中挑选出：是完全平方数同时末尾数字是4的这样特点的数。例如素数：1399，加上45后，得到新数1444。而令1444满足：它是完全平方数，同时末尾数字为4。
现给出任意自然数M～N的区间，请同学们计算并输出所有满足上述条件的数值，并统计个数。

输入

只有一行，包含两个用空格隔开的任意自然数M和N，（其中令1000≤M

输出

共有若干行：前若干行：每行一个数，为满足上述条件的数值；最后一行：只有一个数，为满足上述条件的数值的个数。

样例输入 Copy

1000 4000

样例输出 Copy

1444
2704
3364
3

题意：

||--现给出任意自然数M～N的区间，请同学们计算并输出所有满足上述条件的数值，并统计个数。--||

        说明  素数+45后的新值  属于 【m，n】的范围   而不是素数本身

题解：

01  考虑到  用完全平方数构造的数据量 < 用素数构造的数据量    所以用完全平方数作为构造数据的条件

02  注意用新值判断范围  而不是素数

03  以下用了两种方法  （ 法2 优于 法1 ）

法1：

//  法1 --- 完全平方数  构造数据 
#include
#include

// 判断是否为素数 
int prime( int n )
{
	int i,temp;
	
	temp=(int)sqrt( n );
	
	for( i=2;i<=temp;i++ )
	{
		if( n%i==0 ) return 0;
	}
	return 1;
}

int main()
{
	int m,n,i,ans,remain,flag,square;
	
	while( ~scanf("%d%d",&m,&n) )
	{
		ans=0;
		
		for( i=30;i<=100;i++ )
		{
			square=i*i;
			
			if( square>n ) break;
			
			// 小心漏判边界 
			if( square>=m )
			{
				// 个位 
				remain=square%10;
			
				if( remain==4 )
				{
					flag=prime( square-45 );
					
					if( flag ) 
					{
						printf("%dn",square);
						ans++;
					}
				}
			}
		}
		printf("%dn",ans);
	}
	
	return 0;
}

法2：

//  法2 --- 完全平方数 函数打表 保存所有可能的结果 
#include
#include

// 判断是否为素数 
int prime( int n )
{
	int i,temp;
	
	temp=(int)sqrt( n );
	
	for( i=2;i<=temp;i++ )
	{
		if( n%i==0 ) return 0;
	}
	return 1;
}

// 保存所有可能的结果 
int ans[10];

// 用完全平方数 作为构造条件 （ 比素数 条件的数据要少 ） 
void form()
{
	int i,pos=0,temp;
	
	for( i=30;i*i<1000;i++ );
	
	for( ;i<=100;i++ )
	{
		temp=i*i;
		
		if( temp%10==4 )
		{
			if( prime( temp-45 ) ) ans[pos++]=temp;
		}
	}
}

int main()
{
	int m,n,i,count;
	
	// 打表 
	form();
	
	while( ~scanf("%d%d",&m,&n) )
	{
		count=0;
		
//		for( i=0;ans[i] 
 
 
 
个人见解  酌情采纳.