AcWing 196. 质数距离
原题链接
中等
作者:
cyz3209
,
2021-04-12 20:40:40
,
所有人可见
,
阅读 320
import java.util.*;
public class Main {
public static void main(String[] args) {
new Solution().fun();
}
}
class Solution {
public void fun() {
Scanner scanner = new Scanner(System.in);
choose_zhishu shu = new choose_zhishu();
while(scanner.hasNextLong() && scanner.hasNextLong()) {
long l = scanner.nextLong();
long r = scanner.nextLong();
shu.init((long)50010);
for(long i = 0; i < shu.cnt; i ++) {
long p = shu.primes[(int)i];
long p0 = Math.max(2 * p, (l + p - 1) / p * p);
for(long j = p0; j <= r; j += p) {
if(j > r) break;
if(j - l >= 0)
shu.st[(int)(j - l)] = true;
else break;
}
}
shu.cnt = 0;
for(long j = l; j <= r; j ++) {
if(j - l >= 1000010) break;
if(shu.st[(int)j - (int)l]) continue;
if(j == 1) continue;
shu.primes[(int)shu.cnt] = j;
shu.cnt ++;
}
if(shu.cnt < 2) {
System.out.println("There are no adjacent primes.");
} else {
long minp = 0, maxp = 0;
for(long i = 0; i < shu.cnt - 1; i ++) {
if(shu.primes[(int)i + 1] - shu.primes[(int)i] > shu.primes[(int)maxp + 1] - shu.primes[(int)maxp]) maxp = i;
if(shu.primes[(int)i + 1] - shu.primes[(int)i] < shu.primes[(int)minp + 1] - shu.primes[(int)minp]) minp = i;
}
//2,3 are closest, 7,11 are most distant.
System.out.print(shu.primes[(int)minp] + "," + shu.primes[(int)minp + 1] + " are closest, ");
System.out.println(shu.primes[(int)maxp] + "," + shu.primes[(int)maxp + 1] + " are most distant.");
}
}
}
}
class choose_zhishu {
public long N = (long)1000010;
long[] primes = new long[(int)N];
long cnt; // 质数队列
boolean[] st = new boolean[(int)N]; // false表示下表的数字是质数
public void init(long n) {
for(long i = 0; i < N; i ++) st[(int)i] = false;
for(long i = 0; i < cnt; i ++) primes[(int)i] = 0;
cnt = 0;
for(long i = 2; i <= n; i ++) {
if(!st[(int)i]) primes[(int)cnt ++] = i;
for(long j = 0; primes[(int)j] * i <= n; j ++) {
st[(int)primes[(int)j] * (int)i] = true;
if(i % primes[(int)j] == 0) break;
}
}
for(long i = 0; i < N; i ++) st[(int)i] = false;
}
}