第14课 函数、质数

质数判断的函数

质数，也叫素数。运用五年级数学学过的质数判断方法，可以实现一个判断质数的函数方法：

bool isPrime(int number){                //number是质数返回true，不是质数返回false
	int i;
	if(number<2){
		return false;
	}
	for(i=2;i<=number/2;i++){         //遍历到输入数字除以2，也可以到number开方
		if(number%i==0){
			return false;
		}
	}
	return true;
} 

Q3.单词替换

单词的操作，我们要熟练掌握C语言的<cstring>或是C++中的string类。

Q4.笨小猴

方法一：以单词中的每个字母为目标，分别遍历一次单词，统计这个字母的出现的次数。

	int i,j,maxn=-1,minn=501,sum=0,len; 
	char a[501];
	cin>>a;                         //单词没有空格，可以用cin输入
	len=strlen(a);
	for(i=0;i<len;i++){             //以每个字母为目标分别查找一次
		sum=0;
		for(j=0;j<len;j++){    //从头到位查找这个字母出现的次数
			if(a[i]==a[j]){
				sum++;
			}
		}
		if(sum!=0&&sum<minn){
			minn=sum;
		}
		if(sum!=0&&sum>maxn){
			maxn=sum;
		}
	}
	
	if(isPrime(maxn-minn)){
		cout << "Lucky Word" << endl;
		cout << maxn-minn << endl;
	}else{
		cout << "No Answer" << endl;
		cout << 0 << endl;
	}

判断是否是质数的函数，请参考本课开头部分。

方法二：方法一的统计方法有两层循环，每次循环的次数是字母的长度。按照任务的要求，单词最长是100个字母，那么最大的运算次数是100*100=10000次。如果单词的字母数是100000，那么运算次数达到10⁶*10⁶=10¹²，那么继续使用上面的方法运算时间可能超时，我们可以使用一个数组来存储每个字母的出现次数，只要遍历一次数组就可以将左右的字母统计完。

	int maxn=-1,minn=501,len,b[201]={0}; 
	char a[501];
	cin>>a; 
	len=strlen(a);
	for(int i=0;i<len;i++){
		b[a[i]]++;           //将b数组对应字符的位置+1  
		if(b[a[i]]<minn){
			minn=b[a[i]];
		}
		if(b[a[i]]>maxn){
			maxn=b[a[i]];
		}
	}
	
	if(isPrime(maxn-minn)){
		cout << "Lucky Word" << endl;
		cout << maxn-minn << endl;
	}else{
		cout << "No Answer" << endl;
		cout << 0 << endl;
	}