Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define sz 1000008
  4. int main() {
  5. long long low,high;
  6. vector <long long > primes ;
  7. vector <long long > vec;
  8. bool check[sz];
  9. bool mark[sz];
  10. //freopen("inputuva.txt","r",stdin);
  11. while( scanf("%I64d%I64d",&low,&high)!= EOF) {
  12. long long limit = sqrt(high);
  13. memset(mark,0,sizeof(mark));
  14. mark[0] = 1;
  15. mark[1] = 1;
  16. for ( long long i = 4 ; i <= limit ; i = i+2)
  17. mark[i] = 1 ;
  18.  
  19. for ( long long i = 3 ; i*i <= limit ; i = i+2) {
  20. if ( mark[i] == 0) {
  21. for ( long long j = i*i ; j <= limit ; j = j+i+i) {
  22. mark[j] = 1 ;
  23. }
  24. }
  25. }
  26.  
  27. for ( long long i = 1 ; i <= limit ; i++)
  28. if ( mark[i] == 0) primes.push_back(i);
  29.  
  30. if ( primes.size() == 0) printf("There are no adjacent primes.\n");
  31. else {
  32. memset(check,0,sizeof(check));
  33. long long lolim;
  34. for ( long long i = 0 ; i < primes.size() ; i++) {
  35. if (primes[i] < low) {
  36. if ( low % primes[i] == 0) lolim = low ;
  37. else lolim = primes[i]*((low/primes[i])+1);
  38. }
  39. else lolim = (primes[i]*primes[i]);
  40. for ( long long j = lolim ; j <= high ; j = j + primes[i]) {
  41. check[j-low] = 1 ;
  42.  
  43. }
  44. }
  45. if ( low == 1) check[0] = 1;
  46.  
  47.  
  48. for ( long long i = 0 ; i <= high-low ; i++)
  49. if ( check[i] != 1) vec.push_back(i+low);
  50.  
  51.  
  52. if ( vec.size() < 2) printf("There are no adjacent primes.\n");
  53. else {
  54.  
  55. long long maximum = -1 ,minix,miniy,maxx,maxy;
  56. long long minimum = 100000000;
  57. for ( long long i = 1 ; i < vec.size(); i++) {
  58. if ( vec[i] - vec[i-1] > maximum ) {
  59. maximum = vec[i] - vec[i-1];
  60. maxx = vec[i-1];
  61. maxy = vec[i];
  62. }
  63.  
  64. if ( vec[i] - vec[i-1] < minimum ) {
  65. minimum = vec[i] - vec[i-1];
  66. minix = vec[i-1];
  67. miniy = vec[i];
  68. }
  69. }
  70. printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",minix,miniy,maxx,maxy);
  71. }
  72. }
  73. primes.clear();
  74. vec.clear();
  75. }
  76. return 0 ;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement