poj_2689_Prime Distance
2024-09-07 02:01:07
The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Input
Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.
Output
For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.
Sample Input
2 17
14 17
Sample Output
2,3 are closest, 7,11 are most distant.
There are no adjacent primes. 主要思想是偏移数组,区间素数打表。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
typedef long long LL;
#include<algorithm>
using namespace std;
#define N 1000010
int notprime[N];
int prime[N];
int prime2[N];
bool vis[N];
bool val[N];
int pn=0; void getPrime()
{
memset(prime,0,sizeof(prime));
for(int i=2;i<=N;i++)
{
if(!prime[i])prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&prime[j]<=N/i;j++)
{
prime[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
void getPrime2(int L,int R)
{
memset(notprime,false,sizeof(notprime));
if(L<2)L=2;
for(int i=1;i<=prime[0]&&(long long)prime[i]*prime[i]<=R;i++)
{
int s=L/prime[i]+(L%prime[i]>0);
if(s==1)s=2;
for(int j=s;(long long)j*prime[i]<=R;j++)
if((long long)j*prime[i]>=L)
notprime[j*prime[i]-L]=true;
}
prime2[0]=0;
for(int i=0;i<=R-L;i++)
if(!notprime[i])
prime2[++prime2[0]]=i+L;
} int main()
{
getPrime();
LL m,t,h;
int l,r;
while(~scanf("%d%d",&l,&r))
{
int sh1=0,sh2=1000000,lo1=0,lo2=0;
getPrime2(l,r);
if(prime2[0]<2)
{
puts("There are no adjacent primes.");
continue;
}
for(int i=1;i<prime2[0];i++)
{
if(sh2-sh1>prime2[i+1]-prime2[i])
{
sh1=prime2[i];
sh2=prime2[i+1];
}
if(lo2-lo1<prime2[i+1]-prime2[i])
{
lo1=prime2[i];
lo2=prime2[i+1];
}
}
printf("%d,%d are closest, %d,%d are most distant.\n",sh1,sh2,lo1,lo2);
}
}
最新文章
- ELK日志分析系统搭建(转)
- IOS第三方字体
- ActionResult,PartialViewResult,EmptyResult,ContentResult
- ASP.NET线程与异步
- flex
- MySQL搜索: WHERE 多条件
- 无法关闭的QT程序——思路开阔一下,原来这么简单!
- jQuery.validate 中文 API
- Reactive Extensions
- 每周分享之 二 http协议(3)
- [BZOJ]1027 合金(JSOI2007)
- 大名鼎鼎的Requests库用了什么编码风格?
- 学习Python3 天眼查 爬虫
- Bresenham算法的实现思路
- 爬虫笔记之自如房屋价格图片识别(价格字段css背景图片偏移显示)
- 整理:iOS 短信与电话事件的获取
- linux下elasticsearch 安装、配置及示例
- Linux 性能监控 : CPU 、Memory 、 IO 、Network
- .net程序员书单
- oracle安装完成后目录中不论有没有tnsnames.ora和listener.ora文件 PLSQL都能连上的问题解决方法