C++——素数（质数）专题训练3

作者有话说：中午间隙，新增一道还不错的质数题目。

反质数

【题目描述】（求解因数个数，小规模版）

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。即整数1的因子个数为1个，整数6的因子个数为4个。

如果某个正整数x满足：g(x) > g(i)   0

比如：对于整数 1 2 3 4 5 6 而言，它们的因子个数分别为 1 2 2 3 2 4 ，因此只有 1 ，2  ， 4  ，6 为反质数。

因为对于整数2而言，2的因子个数比它前面正整数的因子和都大，整数3和整数2的因子和个数相等，因此整数3不是反质数。

现在给定一个数N，你能求出不超过N的最大的反质数么？

【输入】

一个数N（1<=N<=1000）。

【输出】

不超过N的最大的反质数。

【样例输入】

1000

【样例输出】 

840

易错点：

大部分学生对反质数的概念容易混淆，满足反质数的条件是：反质数的因子个数要大于比它小的所有整数的因子个数，而不是仅仅前一个数的因子个数！

#include
using namespace std;
int main()
{ 
    int n,g[1001],s=0,f,max=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	s=0;//每判断一个整数的因子数量需要清零 
    	for(int j=1;j<=i;j++)
    	{
    		if(i%j==0) s++;//计算因子个数 
		}
		g[i]=s;//存入一位数组 
	}
	for(int i=1;i<=n;i++)
	{
		if(g[i]>max)//满足反质数的条件：g(x)>g(i)  0 

优化版：
 
#include
using namespace std;
int g[1001];//保证一维数组清零 
int main()
{ 
    int n,f,max=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=i;j++)
    	{
    		if(i%j==0) g[i]++;//计算因子个数 存放在数组中 
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(g[i]>max)//满足反质数的条件：g(x)>g(i)  0