fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXPR = (int)1e8;
  5. vector<int> primes;
  6. void calcPrimes() {
  7.     auto sum = 2LL;
  8.     int cnt = 1;
  9.  
  10.     const int S = round(sqrt(MAXPR));
  11.     vector<char> sieve(S + 1, true);
  12.     vector<array<int, 2>> cp;
  13.     for (int i = 3; i < S; i += 2) {
  14.         if (!sieve[i])
  15.             continue;
  16.         cp.push_back({i, (i * i - 1) / 2});
  17.         for (int j = i * i; j <= S; j += 2 * i)
  18.             sieve[j] = false;
  19.     }
  20.     primes.push_back(0);
  21.     primes.push_back(2);
  22.     //vector<char> block(S);
  23.     std::bitset<10001> block;
  24.     int high = (MAXPR - 1) / 2;
  25.     for (int low = 0; low <= high; low += S) {
  26.         //fill(block.begin(), block.end(), true);
  27.         block.set();
  28.         for (auto &i : cp) {
  29.             int p = i[0], idx = i[1];
  30.             for (; idx < S; idx += p)
  31.                 block[idx] = false;
  32.             i[1] = idx - S;
  33.         }
  34.  
  35.         if (low == 0)
  36.             block[0] = false;
  37.         for (int i = 0; i < S && low + i <= high; i++)
  38.             if (block[i]){
  39.                 ++cnt, sum += (low + i) * 2 + 1;
  40.                 primes.push_back((low + i) * 2 + 1);
  41.             }
  42.     };
  43. }
  44. vector<uint> trig;
  45. void init(){
  46. 	for(uint i=1;i<=3450;i++){
  47. 		trig.push_back(i*(i+1)/2);
  48. 	}
  49. }
  50. inline int scan()
  51.     {
  52.         int z=0;
  53.         char c;
  54.         do{ c=getchar_unlocked(); } while(c<'0');
  55.         for(;c>='0';c=getchar_unlocked()) z = (z<<3) + (z<<1) + (c&15);
  56.         return z;
  57.     }
  58.  inline void fastWrite(unsigned a,unsigned b)
  59. {
  60.     char snum[32];
  61.     int i=0;
  62.     do
  63.     {
  64.         snum[i++]=a%10+'0';
  65.         a=a/10;
  66.     } while(a);
  67.     snum[i++]=' ';
  68.      do
  69.     {
  70.         snum[i++]=b%10+'0';
  71.         b=b/10;
  72.     }
  73.     while(b);
  74.     i=i-1;
  75.     while (i>=0)
  76.         putchar_unlocked(snum[i--]);
  77.     putchar_unlocked('\n');
  78. }
  79. int main()
  80. {
  81. 	unsigned tc;
  82. 	unsigned n;
  83. 	calcPrimes();
  84. 	//init();
  85. 	int x=0,y=0,v=0,lb=0,z=0,ans =0,c;
  86. 	tc = scan();
  87. 	while(tc--)
  88. 	{   
  89.  
  90. 	    n = scan();
  91. 		c = lower_bound(primes.begin(),primes.end(), n)-primes.begin();
  92.  
  93. 		if (n==primes[c]){
  94. 			lb = c;
  95. 			y = 0;
  96. 		        x = sqrt(lb);
  97. 			while(y < lb)
  98. 			{
  99. 				y = x*(x+1);
  100. 				y>>=1;
  101. 				x+=1;
  102. 				v = x;
  103. 			}
  104. 			v = v - 1;
  105. 			z = v-1;
  106. 			ans = lb-((z*(z+1))>>1);
  107. 			fastWrite(ans,v);
  108. 		}else{
  109.            printf("-1\n");
  110. 		}
  111. 	}
  112. 	return 0;
  113. }
  114.  
Success #stdin #stdout 0.34s 36908KB
comments (?)
stdin
copy 
3
3
23
4
stdout
copy 
2 1
4 3
-1
https://ideone.com/nY0EQo
language:
C++14 (clang 8.0)
created:
13 hours 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!