题解 2641: 矩形——C语言代码

解题思路:    枚举

              求最大的素数因子，倒也不用全部枚举，可以先求一个上界，从而从上界往下枚举。因为两个因子均为素数，故因子不等于1，直接将S除以2，以减少枚举次数和量的大小。

              
参考代码:

#include<stdio.h>
#include<math.h>		//包含sqrt()函数

_Bool isPrime(int n){		//判断是否为素数
	if(n<2)		//非素数返回，同时也避免自己测试时输入错误
		return 0;
	int i,root=sqrt(n);
	for(i=2;i1;--i)		//素数因子的最大可能值为S/2
		if(S%i==0)	        //找到一个因子后找另一个因子
			for(j=2;j<root;++j)
				if(isPrime(j)){
					printf("%d",i);
					return 0;
				}
	
	return 0;
}

                这个程序是纯暴力，每次找第二个因子时都要从2开始调用isPrime()函数，时间花费较大，因此写了另一个程序。另一个程序是通过isPrime()函数找到从2到S/2的所有素数并存在数组里，之后的枚举因子就变成了数组的遍历查找。

                但是因为写的时间较短，没有经过严密地思考，程序还有些疏漏，过不了评测，应该是访问了未知空间，但在普通的编辑器上运行还是没什么问题的。我用大大小小的数据测试都可以短时间内运行，代码如下：

#include<stdio.h>
#include<math.h>
#define MAXN 50000	//一个不大的数组空间

int prime[MAXN]={0};	//存放素数
int cur=0;			//游标，这里主要用来记录素数个数

_Bool isPrime(int n){
	if(n<2)
		return 0;
	int i,root=sqrt(n);
	for(i=2;i<=root;++i){
		if(n%i==0)
			return 0;
	}
	prime[cur++]=n;
	return 1;
}

_Bool Find(int n){		//在prime数组中查找当前值
	int i;
	for(i=0;i<cur;++i){
		if(n==prime[i])
			return 1;
	}
	return 0;
}

int main(){
	int i,j,S;
	scanf("%d",&S);
	for(i=2;i=0;--i)
		if(S%prime[i]==0)
			for(j=0;j<=i;++j)
				if(Find(j)){
					printf("%d",prime[i]);
					return 0;
				}
	
	return 0;
}