题目
The prime numbers are not regularly spaced. For example from 2
to 3
the gap is 1
. From 3
to 5
the gap is 2
. From 7
to 11
it is 4
. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43
A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes (see: http://mathworld.wolfram.com/PrimeGaps.html).
We will write a function gap with parameters:
g
(integer >= 2) which indicates the gap we are looking for
m
(integer > 2) which gives the start of the search (m inclusive)
n
(integer >= m) which gives the end of the search (n inclusive)
In the example above gap(2, 3, 50)
will return [3, 5] or (3, 5) or {3, 5}
which is the first pair between 3 and 50 with a 2-gap.
So this function should return the first pair of two prime numbers spaced with a gap of g
between the limits m
, n
if these numbers exist otherwise nil or null or None or Nothing
(depending on the language).
In C++ return in such a case {0, 0}
. In F# return [||]
. In Kotlin return []
#Examples: gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}
gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]. In Kotlin return
[]`
gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}
([193, 197] is also such a 4-gap primes between 130 and 200 but it’s not the first pair)
gap(6,100,110) --> nil or {0, 0}
: between 100 and 110 we have 101, 103, 107, 109
but 101-107
is not a 6-gap because there is 103
in between and 103-109
is not a 6-gap because there is 107
in between.
题解
看讨论区说这道题不能用for循环,还在想是不是MillerRabin素性判定过不了==,结果标准解法不就是一个for循环吗_(:з」∠)_
import java.util.*; import java.io.*; class GapInPrimes { static long pow_mod(long x,long y,long mod) { long res = 1; while (y!=0) { if ((y&1) == 1) res = res * x % mod; x = x*x%mod; y >>= 1; } return res; } static boolean Miller_Rabbin(long n,int a) { if ((n%a) == 0)return false; int r=0; long d=n-1; while ((d&1) == 0) { d>>=1; r++; } long k=pow_mod(a,d,n); if (k==1)return true; for (int i=0;i<r;i++) { if (k==n-1)return true; k=k*k%n; } return false; } static int[] prime_test = {2,3,5,7,11,13,17,23,27,31,37}; static boolean isPrime(long x) { if (x<2)return false; for (int w:prime_test) { if (!Miller_Rabbin(x,w)) { return false; } } return true; } public static long[] gap(int g, long m, long n) { long last = -12345; for (long i=m;i<n;i++) { if (isPrime(i)) { if (i - last == g) { long []result = new long[2]; result[0] = last; result[1] = i; return result; } last = i; } } return null; } }