Guest
Login
跳过导航链接

让程序飞
Time Limit:500MS  Memory Limit:32768K

Description:

本问题要判断整数是否为素数。
程序是处理数据的,为了要让运行速度快,就要算法好。而一个好的算法就是要在单位时间里处理数据的量尽可能大。试比较下列两个程序。

//=====================================
// 判断素数1
//=====================================
#include
using namespace std;
//-------------------------------------
bool isPrime(int n){ // n为素数,返回1; 否则返回0
for(int i=2; i if(n%i==0)
return 0;
return 1;
}//------------------------------------
int main(){
for(int n; cin>>n; )
cout<<(isPrime(n)?”Yes\n”:”No\n”);
}//====================================

该程序可以判断整型int以内的任何整数是否素数。其通过调用一个判断素数函数来完成素数判断的任务,若是素数,程序就输出“Yes”,否则程序就输出“No”。但是该程序对于要处理大量数据时,其速度就不敢恭维了。
如果知道整数范围是216之内,那么可以采用素数状态表的办法,使整数的素数判断变成读取以该整数为下标的数组元素值,以数组元素值的状态1或0来确定整数的素数与否。
只要能够生成素数状态表,就可以使用素数状态表而使程序速度加快。
生成素数状态表的方法用筛法比较快。因而程序可以这样写:

//=====================================
// 判断素数2: 素数状态表法
//=====================================
#include
using namespace std;
//-------------------------------------
// 数组stat为素数状态表(2^16=65536)
// 元素值为0表示其下标为素数,否则为非素数
// 例如: stat[7]为0,则7为素数
// stat[8]为1,则8不是素数
// 状态表初始化为全0(全为素数)
// 通过筛法,将非素数下标的元素值置为1
bool stat[65537] = {0};
//-------------------------------------
int main(){
for(int i=2; i<256; i++){ // 筛法
if(stat[i]==0) // 若i为素数,则其倍数都不是素数,用循环筛掉
for(int j=i*i; j<65536; j+=i)
stat[j] = 1;
}
for(int n; cin>>n; )
cout<<(stat[n]?"Yes\n":"No\n"); // 只需访问stat数组
}//=======================================

请你输入该程序,试运行之,提交之,高效完成素数判断工作。

Input:

一些整数n(1≤n≤2^16)。

Output:

对于每个整数,若为素数,输出Yes,否则输出No。

Sample Input:

121  3  9  7

Sample Output:

No
Yes
No
Yes
Status  Submit


Zhe Jiang University Of Technology Online Programming Space Beta1.3
Designed & Developped By Jin Qiwei
 All Copyright Reserved 2006
937