Codewars Java练习：Gap in Primes

题目

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-107is not a 6-gap because there is 103in between and 103-109is not a 6-gap because there is 107in 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;
	}
}