Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.List;
- import java.util.Scanner;
- class SieveOfEratosthenes {
- int limit;
- int[] isNotPrime; // bitmap
- List<Integer> primeList;
- public SieveOfEratosthenes(int limit) {
- this.limit = limit;
- int halfLimit = (int)(((long)limit+1)>>1);
- int sqrtLimit = (int) Math.sqrt(limit);
- int halfSqrtLimit = (sqrtLimit+1)>>1;
- isNotPrime = new int[(halfLimit+31)>>5];
- isNotPrime[0] |= 1; // 1 is not a prime
- for (int i=1;i<halfSqrtLimit;i++) { // 3, 5, 7, ...
- if (((isNotPrime[i>>5]>>(i&31))&1) == 0) {
- for (int j=(i*(i+1))<<1, k=(i<<1)+1;j<halfLimit;j+=k) {
- isNotPrime[j>>5] |= 1<<(j&31);
- }
- }
- }
- primeList = new ArrayList<Integer>(1000);
- primeList.add(2);
- for (int i=1;i<halfLimit;i++){
- if (((isNotPrime[i>>5]>>(i&31))&1) == 0) {
- int num = (i<<1)+1;
- primeList.add(num);
- //System.out.println(num);
- }
- }
- }
- public boolean isPrime(int num) {
- if ((num & 1) == 0 || num < 2) {
- if(num==2)
- return true;
- return false;
- }
- if (num<=limit) {
- int i = (num-1)>>1;
- return ((isNotPrime[i>>5]>>(i&31))&1) == 0;
- }
- int max = (int) Math.sqrt(num);
- for (int p:primeList) {
- if (p > max) {
- break;
- }
- if (num % p == 0) {
- return false;
- }
- }
- return true;
- }
- public List<Integer> getPrimeList(){
- return primeList;
- }
- }
- public class Main {
- Scanner in;
- StringBuilder buf;
- public Main() {
- in = new Scanner(System.in);
- buf = new StringBuilder();
- SieveOfEratosthenes se = new SieveOfEratosthenes((int)Math.sqrt(Integer.MAX_VALUE));
- List<Integer> pList = se.getPrimeList();
- while(in.hasNext()){
- int l = in.nextInt();
- int u = in.nextInt();
- int len = u-l+1;
- boolean[] notPrime = new boolean[len];
- if(l==1){
- notPrime[0] = true;
- }
- for(int p:pList){
- for(int i=l/p*p;i<=u&&i>=0;i+=p){
- if(i-l>=0&&i!=p){
- notPrime[i-l] = true;
- }
- }
- }
- int min = Integer.MAX_VALUE;
- int min1 = 0;
- int min2 = 0;
- int max = -1;
- int max1 = 0;
- int max2 = 0;
- int p = -1;
- for(int i=l;(long)i<=u&&i>=0;i++){ // 拿掉 long 就會錯
- if(!notPrime[i-l]){
- if(p!=-1){
- if(min>i-p){
- min = i-p;
- min1 = p;
- min2 = i;
- }
- if(max<i-p){
- max = i-p;
- max1 = p;
- max2 = i;
- }
- }
- p = i;
- }
- }
- if(min!=Integer.MAX_VALUE){
- buf.append(String.format("%d,%d are closest, %d,%d are most distant.\n", min1, min2, max1, max2));
- } else {
- buf.append("There are no adjacent primes.\n");
- }
- }
- System.out.print(buf);
- }
- public static void main(String[] args) {
- System.setIn(Main.class.getResourceAsStream("sample.in"));
- }
- }
Add Comment
Please, Sign In to add comment