首页 > ACM题库 > HDU-杭电 > hdu 2136 Largest prime factor-数论-[解题报告]C++
2013
12-29

hdu 2136 Largest prime factor-数论-[解题报告]C++

Largest prime factor

问题描述 :

Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.

输入:

Each line will contain one integer n(0 < n < 1000000).

输出:

Each line will contain one integer n(0 < n < 1000000).

样例输入:

1
2
3
4
5

样例输出:

0
1
2
1
3

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2136

题意:问一个数n最大的素因子是第几个素数。

mark:之前一直TLE。素数表不打好会TLE,分解素因子的时候不加sqrt优化也会TLE。。。

先打好100w的素数表,把素数的位序标记好,然后从1到sqrt(n)分解n,得到n最大的素因子后,再看是第几个。

代码:

# include <stdio.h>
# include <math.h>


int IsPrime[1000010] ;
int Primes[1000010] ;
int cnt = 0 ;


void init()
{
    int i, j ;
    for(i = 1 ; i <= 1000000 ; i++) IsPrime[i] = 1 ;
    for(i = 2 ; i <= 1000 ; i++)if (IsPrime[i])
    {
        for (j = i*i ; j <= 1000000 ; j+=i)
            IsPrime[j] = 0 ;
    }
    for(i = 1 ; i <= 1000000 ; i++) if (IsPrime[i])
    {
        IsPrime[i] = cnt ;
        Primes[cnt++] = i ;
    }
}


int calc(int n)
{
    int i, lim = sqrt(n)+1, rtn = 0 ;
    for(i = 1 ; Primes[i] <= lim && n != 1; i++)
    {
        while (n%Primes[i] == 0)
        {
            n/=Primes[i] ;
            rtn = i ;
        }
    }
    if (n == 1) return rtn ;
    return IsPrime[n] ;
}


int main ()
{
    int n ;
    init() ;
    while (~scanf ("%d", &n))
        printf ("%d\n", calc(n)) ;
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/02/02/2335567.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。