Prime Distance
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 11232 | Accepted: 3018 |
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 17 14 17
Sample Output
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
题意:
给出 L,U (1<=L< U<=2,147,483,647),代表区间 [ L,U ],且U - L < 1,000,000。输出区间内的素数两连续距离最小的起点终点和最大的起点终点。
思路:
素数区间筛选。注意判断数的范围。
AC:
#include <cstdio> #include <string.h> #include <algorithm> #define MAX 1000005 using namespace std; typedef long long ll; int a,b,ans; bool pri1[MAX],pri2[MAX]; int min_d,max_d,min_f,min_t,max_f,max_t; void solve() { for(int i = 0;(ll)i * i < b;i++) pri1[i] = true; for(int i = 0;i <= b - a;i++) pri2[i] = true; pri1[0] = pri1[1] = false; for(int i = 2;(ll)i * i <= b;i++) { if(pri1[i]) { for(int j = i;(ll)j * j * i * i <= b;j++) pri1[i * j] = false; for(ll j = max((ll)2,((ll)a + i - 1) / i) * i;j <= b;j += i) pri2[j - a] = false; } } if(a == 1) pri2[0] = false; //若左区间等于1,要另外判断 int last; ans = 0;min_d = MAX;max_d = -1; for(int i = 0;i <= b - a;i++) { if(pri2[i]) { if(ans) { if(i - last < min_d) { min_d = i - last; min_f = last; min_t = i; } if(i - last > max_d) { max_d = i - last; max_f = last; max_t = i; } } last = i; ans++; } } } int main() { //freopen("test.in","r",stdin); while(~scanf("%d%d",&a,&b)) { solve(); if(ans <= 1) puts("There are no adjacent primes."); else printf("%d,%d are closest, %d,%d are most distant.\n" ,min_f + a,min_t + a,max_f + a,max_t + a); } return 0; }
相关推荐
PrimeNumber 素数生成器 V6.0.0.3 18.4KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
超高速的素数筛选法,大数下10^6区间内筛选所有素数仅需30MS!
PrimeNumber 素数生成器 V7.0.0.0 18.7 KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
使用AKS算法检测素数和生成素数. 提供了AKS的6个步骤的方法 绝对原创
primesieve每个筛选质数使用8个字节,因此其内存使用量约为 每个线程的字节数。安装可以使用操作系统的程序包管理器来安装primesieve命令行程序。 为了使用libprimesieve进行开发,您可能需要安装libprimesieve-dev...
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。...
编制具有如下原型的函数prime,用来判断整数n是否为素数:bool prime(int n); 而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数...
PYTHON 求给定范围内质数和 代码。 def get_primes(n): numbers = set(range(n, 1, -1)) primes = [] while numbers: p = numbers.pop() primes.append(p) numbers.difference_update(set(range(p*2, n+1, p))...
质数的筛选.exe
Prime Numbers - The Most Mysterious Figures in Math
而要研究素数规律,首先要取得某一区间的素数集合。对于专业研究人员,可借助工具书等方式实现,而对于广大素数研究爱好者来说,却是难以逾越的障碍,而用 我们这一软件,您只要输入任意两个正整数,点击[开始寻找]...
prime函数判定素数.c
使用筛选法来确定100以内的素数并将其输出 使用时请在dev运行
素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的素数是2。 话不多说,上代码! prime=[] #用一个列表来存储...
这是我个人对原始素数筛选法的一个优化方法,效率提高一倍以上。 (文档内的代码为C/C++代码)
在初学c++时经常碰到关于素数的题,但是按传统做法总是会超时,先用筛选法将素数找出。
以C++为编程语言,筛选法,编写的求一个数以内的素数
这是我个人对原始素数筛选法的一个优化方法,效率提高一倍以上。
另外Prime95还是利用分布式计算搜索梅森素数(有译为梅森质数)的GIMPS客户 端程序。GIMPS的全称是 The Great Internet Mersenne Prime Search.翻译过来的意思是互联网梅森素数大搜索。GIMPS成立于1996年1月目的就是...
C语言项目:查找四位可逆素数、可逆质数、可逆prime数 小功能分类(在对应头文件中): 对整数进行逆序输出:四种实现方式---nixu_zong4.h 判断是否为素数、质数、prime数:prime.h