CSU1030素数槽
2024-08-30 19:44:50
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的素数槽的长度,每个非负整数占一行。
这题目最需要注意的是不能超时,所以需要用到素数打表法来进行符合条件的素数位置,在通过下标相减得到最后的结果
代码如下:
#include <iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
using namespace std; #define MAXN 1300000
int p[MAXN]; void getPrim()
{
memset(p,,sizeof(p));
int n = (int)(sqrt(MAXN+0.5));
for(int i=;i<=n;i++){
for(int j=i+i;j<=MAXN;j+=i) p[j]=;
}
}
int main()
{
int T,k;
cin>>T;
getPrim();
while(T--){
cin>>k; int top=k,floor=k;
while(p[top]==) top++;
while(p[floor]==) floor--;
cout<<top-floor<<endl; }
return ;
}
最新文章
- bzoj2243
- 搞清arguments,callee,caller
- 【转】解决eclipse新导入工程无法run as server
- linux grep,sed,awk和diff的使用
- 浅谈lua
- vs2010 打包 SQL server compact 4.0 驱动程序
- Sql-Server应用程序的高级注入
- java系统库性能优化注意点
- WPF中实现
- How Tomcat Works(十四)补充
- aspx利用cookie值来停止silverlight中的计时器
- C#语言之“中英文混合字符串对齐”的方法【转】
- Windows Server 2008 安装好之后的简单配置
- poj 3450 Corporate Identity
- 答辩系统bug修改记录
- 教育行业app开发新契机,在线教育要从B端出发
- JDFS:一款分布式文件管理实用程序第二篇(更新升级、解决一些bug)
- 关于在git添加远程地址的过程中遇到的问题
- iOS开发中KVC、KVO简介
- CentOS更新源