最大素因子

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 2 描述

GreyAnts最近正在学习数论中的素数，但是现在他遇到了一个难题：给定一个整数n,要求我们求出n的最大素因子的序数,例如：2的序数是1,3的序数是2,5的序数是3，以此类推. 研究数论是需要很大的耐心的，为了惩罚那些没有耐心读完题目的童鞋，我们规定：1的最大素因子序数是0.

输入 有多组测试数据,每一行输入一个数字n.(0<n<=1000000) 输出 在接下来的一行，输出结果. 样例输入

2
3
4
5

样例输出

1
2
1
3

        这道题可把我坑惨了，看着感觉很简单，但是一写就容易TLE~~~还是来说说比较快捷的思路吧。这个思路是根据筛法改造而来。先从2开始，然后将2标记为第一个素数（即将最大素因子序数标为1），接着将2的倍数的最大素因子序数都标为1。然后再到3，将其最大素因子序数标为2，接着将3的倍数的最大素因子序数都标为2（注意，比如6，先前我们已经将其的最大素因子序数标为1，这时又发现6的一个因子3序数比2的大，所以直接将前面的序数覆盖掉）。再到4，由于4已经有了序数了（即被筛选过了），跳过。再到5，……一直到1000000。有了这张表，不管来什么数据我都能一口报出答案（当然不能超过1000000）。

        下面是我的代码（说多了都是泪，来之不易！）

#include <stdio.h>

#define MAX_SIZE 1000000

void Init(int prime[])
{
    int i,j,k=1;
    for(i=2;i<=MAX_SIZE;i++)
    {
        if(prime[i]==0)
        {
            prime[i]=k;
            for(j=2;i*j<=MAX_SIZE;j++)
            {
                prime[i*j]=k;
            }
            k++;
        }
    }
}

int main()
{
    int n;
    int prime[MAX_SIZE+5]={0};
    Init(prime);
    while((scanf("%d",&n))!=EOF)
    {
        printf("%d\n",prime[n]);
    }
    return 0;
}

回头再来看标程，发现标程的代码有些复杂了。

 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

#define MAX 1000005

bool flag[MAX];
int res[MAX],prime[1005],cnt[MAX];

void init()
{
	int len = 0;
	for(int i = 2;i < 1000;++i)
	{
		if(!flag[i])
		{
			prime[len++] = i;
			for(int j = i * i;j < 1000003;j += i)
				flag[j] = 1;
		}
	}
	for(int i = 2;i < 1000003;++i)
		if(!flag[i]) res[i] = cnt[i] = cnt[i-1] + 1;
		else cnt[i] = cnt[i-1];
}
int judge(int i)
{
	if(i == 1 || res[i]) return res[i];
	int x,p;
	if(!flag[i]) res[i] = cnt[i];
	else 
	{
		x = i;p = 0;
		while(flag[x])
		{
			while(x % prime[p] == 0 && x != prime[p]) x /= prime[p];
			p++;
		}
		res[i] = res[x];
	}
	return res[i];
}
int ssca(int n)
{
	char ch;
	int m = n;
	while(1)
	{
		ch = getchar();
		if(ch == ' ' || ch == '\n')
			return m;
		m = m * 10 + ch - '0';
	}
}
int main()
{
	//freopen("1.txt","r",stdin);
	//freopen("2.txt","w",stdout);
	init();
	int m;
	char ch;
	while(~scanf("%c",&ch))
	{
		m = ssca(ch-'0');
		printf("%d\n",judge(m));
	}
	return 0;
}        

乍一看，就感觉十分复杂，算了，还是不仔细琢磨了。