建立素数表，分解质因数
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 阅读(96)
评论(0) 编辑 收藏 引用