随笔 - 32  文章 - 2  trackbacks - 0
<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8793
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

建立素数表,分解质因数
 1 #include <iostream>
 2 using namespace std;
 3 int n,m;
 4 int su[5500],sn;
 5 bool he[50001];
 6 int num[5500];
 7 void work(int x){
 8     int d=x;
 9     x+=d;
10     while (x<=5e4){
11         he[x]=true;
12         x+=d;
13         }
14     }
15 void calc(int x,int c){
16     int p=1;
17     while (x>1){
18         int count=0;
19         while (x%su[p]==0&&x>1){
20             x/=su[p];
21             ++count;
22             }
23         num[p]+=count*c;
24         ++p;
25         }
26     }
27 int main(){
28     for (int i=2;i<=5e4;++i) if (!he[i]) work(i);
29     for (int i=2;i<=5e4;++i) if (!he[i]) su[++sn]=i;
30     scanf("%d%d",&n,&m);
31     for (int i=0;i<m;++i) calc(n-i,1);
32     for (int i=m;i>0;--i) calc(i,-1);
33     int ans=0;
34     for (int i=1;i<=sn;++i) if (num[i]>0++ans;
35     cout<<ans;
36     }
37 

posted on 2008-11-07 16:24 Joseph 阅读(104) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理