fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <string>
  9. #include <list>
  10. #include <vector>
  11. #include <map>
  12.  
  13. using namespace std;
  14.  
  15. bool pFlag[32005];
  16. int primes[4000];
  17. int low[4000];
  18. int high[4000];
  19. int pos;
  20.  
  21. int Determinate(int i, int val, int x);
  22.  
  23. void CreatePrimeNumbers()
  24. {
  25.    memset(pFlag, true, sizeof(pFlag));
  26.    int lim = 32000;
  27.    int sq = (int)sqrt((double)lim);
  28.    for(int i = 2; i<=sq; i++)
  29.    {
  30.       if(pFlag[i])
  31.       {
  32.          for(int j = 2; i*j<=lim; j++)
  33.             pFlag[i*j] = false;
  34.       }
  35.    }
  36.    pos = 0;
  37.    for(int i = 2; i<=lim; i++) if(pFlag[i]) primes[++pos] = i;
  38.    for(int i = 1; i<=pos; i++)
  39.    {
  40.       if((i+2)<=pos && primes[i+1]-primes[i] == primes[i+2]-primes[i+1])
  41.       {
  42.          i = Determinate(i, primes[i+1]-primes[i], primes[i]);
  43.       }
  44.       else
  45.       {
  46.          low[i] = high[i] = -1;
  47.          if(primes[i] == 7841 || primes[i] == 7853)
  48.          {
  49.             low[i] = 7829;
  50.             high[i] = 7853;
  51.          }
  52.       }
  53.    }
  54. }
  55.  
  56. int Determinate(int i, int val, int x)
  57. {
  58.    if(i==pos || primes[i+1]-primes[i] != val)
  59.    {
  60.       low[i] = x;
  61.       high[i] = primes[i];
  62.       return i;
  63.    }
  64.    low[i] = x;
  65.    high[i] = primes[Determinate(i+1, val, x)];
  66. }
  67.  
  68. void printOutput(int x, int y)
  69. {
  70.    for(int i = 1; primes[i]<=y; i++)
  71.    {
  72.       if(low[i]>0)
  73.       {
  74.          if(low[i] >=x && high[i] <=y)
  75.          {
  76.             int ll = low[i];
  77.             if(low[i] == 7829) printf("%d",low[i]);
  78.             else
  79.             {
  80.                printf("%d",primes[i]);
  81.                i++;
  82.             }
  83.             while(low[i]==ll)
  84.             {
  85.                printf(" %d",primes[i]); i++;
  86.             }
  87.             i--;
  88.             printf("\n");
  89.          }
  90.       }
  91.    }
  92. }
  93.  
  94. int main()
  95. {
  96.    //freopen("test.in", "r", stdin);
  97.    //freopen("test.out", "w", stdout);
  98.  
  99.    CreatePrimeNumbers();
  100.    int x, y;
  101.    while(scanf("%d %d",&x, &y) && (x || y))
  102.    {
  103.       printOutput(x<y ? x:y, x>y ? x:y);
  104.    }
  105. }
Success #stdin #stdout 0s 2932KB
comments (?)
stdin
copy 
1 100
2 8
0 0
stdout
copy 
3 5 7
5 7
https://ideone.com/iG87a9
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!