首页 > 代码库 > 数论 - 素数的运用 --- poj 2689 : Prime Distance
数论 - 素数的运用 --- poj 2689 : Prime Distance
Prime Distance
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 12512 | Accepted: 3340 |
Description
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 1714 17
Sample Output
2,3 are closest, 7,11 are most distant.There are no adjacent primes.
Source
Waterloo local 1998.10.17
Mean:
输入两个数l和r,要你找出l~r范围内相邻的最近的素数。
analyse:
这题的数据范围很大。
我们首先来分析，int范围内(2147483647)的素数都可以用根号(2147483647)内的素数全部筛出来，那就用埃拉托斯尼斯筛法这个范围内的素数都筛出来。然后再来排除l~r范围内的合数就可。其中有一个小技巧，避免了超时。
Time complexity：O(50000*m),其中m为素数的个数。
Source code：
/* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---‘\____ .‘ \\| |// `. / \\||| : |||// / _||||| -:- |||||- | | \\\ - /// | | | \_| ‘‘\---/‘‘ | | \ .-\__ `-` ___/-. / ___`. .‘ /--.--\ `. . __ ."" ‘< `.___\_<|>_/___.‘ >‘"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-‘====== `=---=‘^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^............................................. 佛祖镇楼 BUG辟易 佛曰: 写字楼里写字间，写字间里程序员； 程序人员写程序，又拿程序换酒钱。 酒醒只在网上坐，酒醉还来网下眠； 酒醉酒醒日复日，网上网下年复年。 但愿老死电脑间，不愿鞠躬老板前； 奔驰宝马贵者趣，公交自行程序员。 别人笑我忒疯癫，我笑自己命太贱； 不见满街漂亮妹，哪个归得程序员？*///Memory Time// 1347K 0MS// by : Snarl_jsb#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 50005#define LL long longusing namespace std;bool v[N*20];LL p1[N],p2[N];LL c1,c2,d1,d2;LL l,r,num,idx,b,t;void make_p1(){ num=-1; for(LL i=2;i<N;++i) { if(!v[i]) { p1[++num]=i; } for(LL j=0;j<=num&&i*p1[j]<N;++j) { v[i*p1[j]]=1; if(i%p1[j]==0) break; } }// cout<<num<<endl;}void make_p2(){ idx=-1; memset(v,0,sizeof(v)); for(LL i=0;i<=num;++i) { b=l/p1[i]; while(b*p1[i]<l||b<=1) //一个关键的剪枝，不用会超时 b++; for(LL j=b*p1[i];j<=r;j+=p1[i]) { if(j>=l&&j<=r) { v[j-l+1]=1; } if(j>r) break; } } for(LL i=l;i<=r;++i) { if(!v[i-l+1]&&i>1) { p2[++idx]=i; } }}void solve(){ make_p2(); LL minn=INT_MAX,maxx=INT_MIN; for(LL i=1;i<=idx;++i) { t=p2[i]-p2[i-1]; if(t<minn) { minn=t; c1=p2[i-1]; c2=p2[i]; } if(t>maxx) { maxx=t; d1=p2[i-1]; d2=p2[i]; } }}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.txt","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout); make_p1(); while(~scanf("%I64d %I64d",&l,&r)) { solve(); if(idx<1) puts("There are no adjacent primes."); else { printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",c1,c2,d1,d2); } } return 0;}
数论 - 素数的运用 --- poj 2689 : Prime Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。