UVA10140 Prime Distance
2024-09-29 11:05:29
UVA10140 Prime Distance
给定两个整数L,R(1<=L<=R<=2^{31},R-L<=10^6)L,R(1<=L<=R<=231,R−L<=106),求闭区间 [L,R][L,R] 中相邻两个质数的差的最小值和最大值是多少,分别输出这两个质数。
首先我们发现:R-LR−L 的范围很小,我们应该要能够快速求出 L\sim RL∼R 之间的质数。
显然有推论:任意一个合数 xx 必定包含一个不超过 \sqrt xx 的质因子。
所以我们可以筛出 [1,\sqrt R][1,R] 之间的所有质数,对于每个质数 pp,把 [L,R][L,R] 中能被 pp 整除的数标记为合数。最终没有被标记的数就是质数,对相邻的质数两两比较,找出差值最小和最大的即可。
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; typedef long long LL;
#define res register int
const LL N=1e6+100;
LL v[N],p[N],tot;
LL L,R; inline LL max(LL a,LL b){return a>b?a:b;}
inline LL min(LL a,LL b){return a<b?a:b;} inline void primes(LL n)
{
memset(v,0,sizeof(v)); tot=0;
for(res i=2 ; i<=n ; i++)
{
if(!v[i]) v[i]=i,p[++tot]=i;
for(res j=1 ; j<=tot ; j++)
{
if(p[j]>n/i || p[j]>v[i]) break;
v[i*p[j]]=p[j];
}
}
} LL a[N],cnt;
LL vis[N];
int main()
{
primes(N);
while(cin>>L>>R)
{
memset(vis,0,sizeof(vis));
for(res i=1 ; i<=tot ; i++)
{
for(res j=L/p[i] ; p[i]*j<=R ; j++)
{
LL x=j*p[i];
if(j>1 && x>=L) vis[x-L]=1;
}
}
if(L==1) vis[0]=1;
cnt=0;
for(res i=L ; i<=R ; i++) if(!vis[i-L]) a[++cnt]=i;
if(cnt<=1) {
puts("There are no adjacent primes.");
continue;
} LL maxn(-1e9),minn(1e9),x,y;
for(res i=1 ; i<cnt ; i++)
if(a[i+1]-a[i]<minn) minn=a[i+1]-a[i],x=a[i],y=a[i+1];
printf("%lld,%lld are closest, ",x,y);
for(res i=1 ; i<cnt ; i++)
if(a[i+1]-a[i]>maxn) maxn=a[i+1]-a[i],x=a[i],y=a[i+1];
printf("%lld,%lld are most distant.\n",x,y);
}
return 0;
}
最新文章
- Atitit &#160;godaddy 文件权限 root权限设置
- C#委托的一次";甜蜜";接触
- MVC -- 后台RedirectToAction传递实体类与字符串
- mysql中正则表达式的使用
- Android Service 与 Thread 的区别
- Spring 中 Xml配置文件属性的说明
- zw版【转发&#183;台湾nvp系列Delphi例程】HALCON TileChannels
- SharePoint 2013 运行在IIS 应用32位错误
- Python 基础语法(四)
- [C# 基础知识梳理系列]专题六:泛型基础篇——为什么引入泛型
- expect set timeout -1 永不超时
- 数据结构-B树
- JavaScript--我发现,原来你是这样的JS:面向对象编程OOP[1]--(理解对象和对象属性类型)
- unshift() 方法将一个或多个元素添加到数组的开头,并返回新数组的长度
- 3、Ansible playbooks(Hosts、Users、tasks、handlers、变量、条件测试(when、迭代)、templates)
- jira与svn的调研
- POJ 1988&;&;2236
- oracle数据库如何创建用户和角色,并给其赋权?
- 5.Resource注解解析
- eclipse debug 错误 之 processWorkerExit