首页 > 代码库 > csu 1030: 素数槽
csu 1030: 素数槽
素数槽
Description
处于相邻的两个素数p和p + n之间的n - 1个连续的合数所组成的序列我们将其称为长度为n的素数槽。比如,?24, 25, 26, 27, 28?是处于素数23和素数29之间的一个长度为6的素数槽。
你的任务就是写一个程序来计算包括整数k的素数槽的长度。假设k本身就是素数,那么觉得包括k的素数槽的长度为0。
Input
第一行是一个数字n,表示须要測试的数据的个数。后面有n行,每行是一个正整数k。k大于1而且小于或等于的第十万个素数(也就是1299709)。
Output
对于输入部分输入的每个k。都相应输出一个非负整数,表示包括k的素数槽的长度。每个非负整数占一行。
Sample Input
5
10
11
27
2
492170
Sample Output
4
0
6
0
114
题意:
两个素数之间所有为连续的合数,一共同拥有n个这种数。那么这个素数槽的个数为n+1。题目给定你一个数,问你这个数在某个素数槽中。求这个素数槽的个数。
思路:
假设输入的数为素数,那么素数槽的个数为0,。假设为合数。就从这个数開始,往左右两边分别递减或递增一个数,每次累计记录,直到遇到素数为止。
代码例如以下:
#include<cstdio> bool p[1299710]; #include<cstring> using namespace std; void prime() { int i,j; memset(p,0,sizeof(p)); for(int i=2;i<=1299709;i++) { if(!p[i]) { for(int j=2;i*j<=1299709;j++) p[i*j]=1; } } } int main() { int n,a,sum,k,t; prime(); scanf("%d",&n); while(n--) { sum=0; scanf("%d",&a); if(!p[a]||a==1) { printf("%d\n",sum); continue; } t=a; while(a--) { if(p[a]) sum+=1; else break; } while(t++) { if(p[t]) sum+=1; else break; } printf("%d\n",sum+2); } return 0; }
csu 1030: 素数槽
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。