NYOJ520 最大素因子

最大素因子

时间限制：1000 ms  |  内存限制：65535 KB

难度：2

 

描述

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

 

输入

有多组测试数据,每一行输入一个数字n.(0<n<=1000000)

输出

在接下来的一行，输出结果.

样例输入

1
2
3
4
5

样例输出

0
1
2
1
3

来源

hdu改编

/*代码一 ：暴力一点一点求的  。。。。华丽丽的超时了
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

bool num[1000001];
int prime[500000];
int Is_prime()
{
    memset(num, true, sizeof(num));
    int count = 1;
    num[0] = num[1] = false;
    for(int i = 2; i <= 1000; ++i)
        for(int j = i * i; j <= 1000000; j += i)
            num[j] = false;
    for(int i = 2; i <= 1000000; ++i)
        if(num[i])
            prime[count++] = i;
    return 0;
}

int main()
{
    int n;
    Is_prime();
    while(~scanf("%d", &n))
    {
        if(n == 1)
        {
            printf("0\n");
            continue;
        }
        int t = 0;
        int cnt = 1;
        while(n >= prime[cnt])
        {
            if(n % prime[cnt] == 0)
            {
                n /= prime[cnt];
                t = cnt;
            }
            ++cnt;
        }
        printf("%d\n", t);
    }
    return 0;
}
*/

// 代码二： 参照别人的思路，在素数筛选法中直接求结果
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000005;
int ans[N];

// 原理：因为任何数都可以分解为由全部素因子乘积的形式
void prime ()
{
    int cnt = 0;
    for(int i = 2; i < N; i++)
        if(ans[i] == 0)  // 说明 i 是素数
        {
            ++cnt;  // cnt 记录 素数 i  出现的序数
            for(int j = i; j < N; j += i)
               //素数的整倍数的最大素因子可能是该素数
                ans[j] = cnt;
                //更新素数对应的呈现的次序
        }
}

int main()
{
    prime();
    int num;
    while(~scanf("%d", &num))
        printf("%d\n", ans[num]);
    return 0;
}