NYOJ 520 解题报告

最大素因子

时间限制: 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;
}        

乍一看,就感觉十分复杂,算了,还是不仔细琢磨了。NYOJ 520 解题报告



上一篇:数论基础(不是


下一篇:华钜同创:Prime Day活动前的这6点建议,你一定要看!