fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. #define N 3000000
  6.  
  7. //bool prime[N];
  8. //int primes[N];
  9. //int semiprimes[2000005];
  10. int main()
  11. {
  12.  
  13.     bool* prime = new bool[N];
  14.     int* primes = new int[N];
  15.     int* semiprimes = new int[2000005];
  16.  
  17.     for(int i=0; i < N ; i++) prime[i] = true;
  18.     int cnt = 0;
  19.     for(int i=2 ; i < N ; i++)
  20.     {
  21.         if(prime[i])
  22.         {
  23.  
  24.             primes[cnt++] = i;
  25.             for(int j = i; j < N ; j+= i)
  26.                 prime[j] = false;
  27.         }
  28.     }
  29.  
  30.  
  31.    // printf("%d\n",primes[cnt-1]);
  32.  
  33.     //for(int i = 0; i < 50 ; i++) printf("%d\n",primes[i]);
  34.  
  35.     int i, j, k = 1;
  36.     int p, q, current_limit;
  37.     int target = 2000000;
  38.     for (i = 0, p = primes[i]; p < target; i++)
  39.     {
  40.         current_limit = target/p;
  41.         for (j = i + 1, q = primes[j]; q <= current_limit; j++)
  42.         {
  43.             k++;
  44.             semiprimes[k++] = p*q;
  45.         }
  46.  
  47.     }
  48.     printf("%d\n",k);
  49.  
  50.  
  51.     int t;
  52.  
  53.     scanf("%d",&t);
  54.     int n;
  55.     while(t--)
  56.     {
  57.         scanf("%d",&n);
  58.         printf("%d\n",semiprimes[n]);
  59.     }
  60.  
  61.     delete[] prime;
  62.     delete[] semiprimes;
  63.     delete[] primes;
  64.  
  65.  
  66.     return 0;
  67. }
  68.  
  69.  
  70.  
  71.  
Runtime error #stdin #stdout 0.09s 25192KB
comments (?)
stdin
copy 
3
1
2
3
stdout
copy 
Standard output is empty
https://ideone.com/7j79o
language:
C++ (gcc 8.3)
created:
11 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!