解题思路:
我写的时间复杂度感觉挺高的,但是竟然没有超时,不知道他的时间复杂度是不是很低。
#define maxn 500010 #include<stdio.h> int a[maxn],b[maxn]; int ptr,n,m,num_a,num_b; void solve() { a[0]=-1; for(int i=1;i<=n;i++) a[i]=a[i-1]+2; b[1]=1;b[2]=3; ptr=2; num_a=n; num_b=2; while(ptr+a[ptr]<=num_a) { num_b=1; for(int i=1;i<=num_a;i++) if(i%a[ptr]!=0) b[num_b++]=a[i]; num_a=num_b-1; for(int i=1;i<=num_a;i++) a[i]=b[i]; ptr++; } } int main(void) { int sum = 0; scanf("%d%d",&m,&n); solve(); for(int i=1;i<=num_a;i++) if(a[i]>m && a[i]<n) sum++; printf("%d",sum); return 0; }
注意事项:
参考代码:
0.0分
0 人评分