当前位置:   article > 正文

素数求和问题_请进行程序设计,找出n个输入数据中的所有素数,对其进行求和运算。输入说明:输入数

请进行程序设计,找出n个输入数据中的所有素数,对其进行求和运算。输入说明:输入数

描述
现在给你N个数(0<N<1000),现在要求你写出一个程序,找出这N个数中的所有素数,并求和。
输入
第一行给出整数M(0<M<10)代表多少组测试数据
每组测试数据第一行给你N,代表该组测试数据的数量。
接下来的N个数为要测试的数据,每个数小于1000
输出
每组测试数据结果占一行,输出给出的测试数据的所有素数和
样例输入
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

解题思路:做这道题时,我的算法超时,借鉴了别人的算法。首先采用筛法选素数,存在一个数组中。输入待判断的数,利用二叉法遍历数组,如果不在数组中,寻找最接近的两 个素数,判断距离寻找最近的素数。


  1. #include<stdio.h>
  2. int a[10000001]={0};
  3. int main()
  4. {
  5. int i,j,len=0;
  6. //对不是素数的进行标记
  7. for(i=2;i<1000001;i++)
  8. if(a[i]==0)
  9. {
  10. for(j=i+i;j<1000001;j=j+i)
  11. a[j]=1;
  12. }
  13. //将素数存进数组中
  14. for(i=2;i<1000001;i++)
  15. if(a[i]==0)
  16. {
  17. a[len]=i;
  18. len++;
  19. }
  20. int T;
  21. scanf("%d",&T);
  22. while(T--)
  23. {
  24. int n,low=0,end=len-1,mid;
  25. scanf("%d",&n);
  26. //二叉法遍历
  27. while(low<=end)
  28. {
  29. mid=(low+end)/2;
  30. if(a[mid]==n)
  31. {
  32. printf("%d 0\n",n);//输入值为素数时,直接输出
  33. break;
  34. }
  35. else if(a[mid]<n)
  36. low=mid+1;
  37. else
  38. end=mid-1;
  39. }
  40. //输入值不为素数,进行判断,此时low>end
  41. if(low>end)
  42. {
  43. if(n==1)
  44. printf("2 1\n");
  45. else if(a[low]-n>=n-a[end])
  46. printf("%d %d\n",a[end],n-a[end]);
  47. else
  48. printf("%d %d\n",a[low],a[low]-n);
  49. }
  50. }
  51. return 0;
  52. }

经验:做过这道题后,学会了筛法选素数,也有了将一个数组中的数进行删除的思路。


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/329030
推荐阅读
相关标签
  

闽ICP备14008679号