HDOJ2136

峰's profile流　　浪　　的　　枫　　之　　羽PhotosBlogLists

< Previous Next >

Problem Description

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.

Input

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

Output

Output the LPF(n).

Sample Input

Sample Output

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

算法思想：采用素数筛选法改进以符合这道题目！

memset(prime, -1, sizeof(prime));
 for(i = 2; i< MAX; i++) 
 {
        if(prime[i]==-1) 
  {
   num++;
   for(j = i; j < MAX; j+=i) 
   {
    prime[j] = num;
   }
        }
 }

December 15 6:52 PM | Blog it | ACM

Comments (1)

To add a comment, sign in with your Windows Live ID (if you use Hotmail, Messenger, or Xbox LIVE, you have a Windows Live ID). Sign in

Don't have a Windows Live ID? Sign up

No namewrote:

Hi, 我已把你收录到博客部落：
部落名: 自动新加入的博客, 部落地址:
http://www.blogblo.com/tribe/show/88

Dec. 17

Trackbacks

The trackback URL for this entry is:

http://eddyzhoufeng.spaces.live.com/blog/cns!DD28D4EF61AE1D45!832.trak

Weblogs that reference this entry

None