Chinaunix首页 | 论坛 | 博客
  • 博客访问: 144566
  • 博文数量: 66
  • 博客积分: 1571
  • 博客等级: 上尉
  • 技术积分: 715
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-24 22:55
文章分类

全部博文(66)

文章存档

2012年(66)

我的朋友

分类: C/C++

2012-08-26 15:34:00

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
1 2 3 4 5
Sample Output
0 1 2 1 3一个数如果是质数,则不可能通过某个数的倍乘去得到它如果不是质数,则可以通过某个小整数的有限次的倍乘得到它

点击(此处)折叠或打开

  1. #include<stdio.h>
  2.   #include<string.h>
  3. int a[1000000]; //题意
  4. int main()
  5.  {
  6.      int i,j,k;
  7.      memset(a,0,100000);
  8. for(i=2,k=0;i<1000000;i++)
  9.     {
  10.    if(!a[i]) // 确保每个数都不重复出现
  11.      {
  12.       k++; // 对于未出现的要+1,递推
  13.      for(j=i;j<1000000;j+=i)
  14.                a[j]=k;
  15.   }
  16.  }
  17.  int n;
  18.   while(scanf("%d",&n)!=EOF)
  19.     {
  20.    printf("%d\n",a[n]);
  21.   }
  22.  return 0;
  23.  }

阅读(1481) | 评论(0) | 转发(0) |
0

上一篇:Cake

下一篇:转 B/S架构 C/S架构 SOA架构

给主人留下些什么吧!~~