Guest User

Untitled

a guest
May 25th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.71 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Scanner;
  4.  
  5. class SieveOfEratosthenes {
  6.  
  7. int limit;
  8.  
  9. int[] isNotPrime; // bitmap
  10.  
  11. List<Integer> primeList;
  12.  
  13. public SieveOfEratosthenes(int limit) {
  14. this.limit = limit;
  15. int halfLimit = (int)(((long)limit+1)>>1);
  16. int sqrtLimit = (int) Math.sqrt(limit);
  17. int halfSqrtLimit = (sqrtLimit+1)>>1;
  18. isNotPrime = new int[(halfLimit+31)>>5];
  19.  
  20. isNotPrime[0] |= 1; // 1 is not a prime
  21.  
  22. for (int i=1;i<halfSqrtLimit;i++) { // 3, 5, 7, ...
  23. if (((isNotPrime[i>>5]>>(i&31))&1) == 0) {
  24. for (int j=(i*(i+1))<<1, k=(i<<1)+1;j<halfLimit;j+=k) {
  25. isNotPrime[j>>5] |= 1<<(j&31);
  26. }
  27. }
  28. }
  29.  
  30. primeList = new ArrayList<Integer>(1000);
  31. primeList.add(2);
  32. for (int i=1;i<halfLimit;i++){
  33. if (((isNotPrime[i>>5]>>(i&31))&1) == 0) {
  34. int num = (i<<1)+1;
  35. primeList.add(num);
  36. //System.out.println(num);
  37. }
  38. }
  39.  
  40. }
  41.  
  42.  
  43. public boolean isPrime(int num) {
  44. if ((num & 1) == 0 || num < 2) {
  45. if(num==2)
  46. return true;
  47. return false;
  48. }
  49.  
  50. if (num<=limit) {
  51. int i = (num-1)>>1;
  52. return ((isNotPrime[i>>5]>>(i&31))&1) == 0;
  53. }
  54.  
  55. int max = (int) Math.sqrt(num);
  56. for (int p:primeList) {
  57. if (p > max) {
  58. break;
  59. }
  60. if (num % p == 0) {
  61. return false;
  62. }
  63. }
  64.  
  65. return true;
  66. }
  67.  
  68. public List<Integer> getPrimeList(){
  69. return primeList;
  70. }
  71.  
  72. }
  73.  
  74. public class Main {
  75.  
  76.  
  77. Scanner in;
  78. StringBuilder buf;
  79.  
  80. public Main() {
  81. in = new Scanner(System.in);
  82. buf = new StringBuilder();
  83.  
  84. SieveOfEratosthenes se = new SieveOfEratosthenes((int)Math.sqrt(Integer.MAX_VALUE));
  85. List<Integer> pList = se.getPrimeList();
  86.  
  87. while(in.hasNext()){
  88. int l = in.nextInt();
  89. int u = in.nextInt();
  90.  
  91. int len = u-l+1;
  92. boolean[] notPrime = new boolean[len];
  93. if(l==1){
  94. notPrime[0] = true;
  95. }
  96.  
  97. for(int p:pList){
  98. for(int i=l/p*p;i<=u&&i>=0;i+=p){
  99. if(i-l>=0&&i!=p){
  100. notPrime[i-l] = true;
  101. }
  102. }
  103. }
  104.  
  105. int min = Integer.MAX_VALUE;
  106. int min1 = 0;
  107. int min2 = 0;
  108.  
  109. int max = -1;
  110. int max1 = 0;
  111. int max2 = 0;
  112.  
  113. int p = -1;
  114.  
  115. for(int i=l;(long)i<=u&&i>=0;i++){ // 拿掉 long 就會錯
  116.  
  117. if(!notPrime[i-l]){
  118. if(p!=-1){
  119. if(min>i-p){
  120. min = i-p;
  121. min1 = p;
  122. min2 = i;
  123. }
  124.  
  125. if(max<i-p){
  126. max = i-p;
  127. max1 = p;
  128. max2 = i;
  129. }
  130. }
  131. p = i;
  132. }
  133. }
  134.  
  135. if(min!=Integer.MAX_VALUE){
  136. buf.append(String.format("%d,%d are closest, %d,%d are most distant.\n", min1, min2, max1, max2));
  137. } else {
  138. buf.append("There are no adjacent primes.\n");
  139. }
  140.  
  141.  
  142. }
  143.  
  144. System.out.print(buf);
  145. }
  146.  
  147. public static void main(String[] args) {
  148. System.setIn(Main.class.getResourceAsStream("sample.in"));
  149. }
  150.  
  151. }
Add Comment
Please, Sign In to add comment