2013
12-29

# 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

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

# 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 ;
}

1. 谁说的，上次我在北京，那段时间经常拉肚子，吃的又少，还工作到晚上10点，回去11点了，就遇到鬼打墙了，短短的路走了半个小时没走出去，幸亏我有点傻福气，问人了，才破了那个局，这东西其实在我们周围，要经常发善心，不做亏心事就不怕

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