赞
踩
3 5 1 2 3 4 5 8 11 12 13 14 15 16 17 18 10 21 22 23 24 25 26 27 28 29 30
10 41 52
解题思路:做这道题时,我的算法超时,借鉴了别人的算法。首先采用筛法选素数,存在一个数组中。输入待判断的数,利用二叉法遍历数组,如果不在数组中,寻找最接近的两 个素数,判断距离寻找最近的素数。
- #include<stdio.h>
- int a[10000001]={0};
-
- int main()
- {
- int i,j,len=0;
- //对不是素数的进行标记
- for(i=2;i<1000001;i++)
- if(a[i]==0)
- {
- for(j=i+i;j<1000001;j=j+i)
- a[j]=1;
- }
- //将素数存进数组中
- for(i=2;i<1000001;i++)
- if(a[i]==0)
- {
- a[len]=i;
- len++;
- }
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n,low=0,end=len-1,mid;
- scanf("%d",&n);
- //二叉法遍历
- while(low<=end)
- {
- mid=(low+end)/2;
- if(a[mid]==n)
- {
- printf("%d 0\n",n);//输入值为素数时,直接输出
- break;
- }
- else if(a[mid]<n)
- low=mid+1;
- else
- end=mid-1;
- }
- //输入值不为素数,进行判断,此时low>end
- if(low>end)
- {
- if(n==1)
- printf("2 1\n");
- else if(a[low]-n>=n-a[end])
- printf("%d %d\n",a[end],n-a[end]);
- else
- printf("%d %d\n",a[low],a[low]-n);
- }
- }
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。