//@shadeware #include <cstdio> #include <vector> #include <cmath> unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0" "5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);} 

//@mikhaelkh #include <cstdio> #include <bitset> unsigned char s[]=" 3ћfСЫБ b”Ђ)Cр ®—іЈ€Я $9шэD » $ѕ|Іш®† %ЃЉЃмF© &_яВГЕЕ 'Y¶FьВµ (nsџИp± )ќлznQ2 *иSР—ж) ,oшtе\\v -пW0BC† /«Ю#™)ґ 1‚ьј”8P 3sю[Y6i 5.qЛ.“ 7¤zMЃшj 9г—‹XyЇ <_‰­XжЅ >ТOh«€Y AЃМ“«n® DKr]µrЩ G.?“нU® J*Ј»‚­Џ M@˜Eп†Ь PpYґпHј S№pvdјя W>дGpІш ZєQЦаЋ~ ^qяmty= bC†,щnт f.d“¤ ¤ j1Ж [|Ј nN№BўЮ: r…ЄG­рр vФiчwЁ{ {_Лз}Lh б*sЁЭ# „ћoї‹УE ‰to]¶е~ Ћd*4:иХ “kѕK8ћш ˜Њ~ќ˜QЄ ќЕЛ7д6« Ј;Ёл0ўь Ё§Iвc§б ®ObЗюЏP імЏxь>† №Е›»ЯPo ї·NцбЬ† ЕБ1ґgп& ЛгlъІcѓ ТAdЎ“[$ Ш–Й:ілЧ Я%юі±Ю1 е«_7бќЌ мlчnєСџ уF”ЭDРЭ ъ8ћуcћЖ $$CМжМMЕ $+gDbцPр $2ЎЧтУ‡E $9цА®П†Ы "; enum{S=1<<14,N=1<<23}; long long a[65],res; std::bitset<S> u; std::bitset<N> v; int n,r,x,i,j; int main() { 	scanf("%d",&n); 	for (i=1;i<65;++i) 		for (++j;s[j]>32;++j) 			a[i]=221*a[i]+s[j]-35; 	*a=2,res=a[j=n/2/N],x=j*2*N,v[0]=!j; 	for (i=3;i<S+S;i+=2) 		if (!u[i/2]) { 			for (j=i*i/2;j<S;j+=i)u[j]=1; 			for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1; 		} 	for(i=1;i<=n-x;i+=2) 		if(!v[i/2])res+=x+i; 	printf("%lld\n", n>1?res:0); }

 //@Icemore #include<iostream> #include<cmath> #include<memory.h> #include<pthread.h> #define lng long long const int T=4,Q=33000,S=100000; bool np[Q],b[T][S]; int p[Q],c,B,s,e; lng A[T],R,P[]={0,1906816620981654LL,7357074544482779LL,16217881619242062LL,28422918403819825LL}; void* f(void*_){ 	long id=(long)_; 	int C=(e/S-B+1)/T,q,M,i,j,k; 	M=(id==T-1)?(e/S+1):(id+1)*C+B; 	for(k=id*C+B;k<M;++k){ 		memset(b[id],0,sizeof(bool)*S);q=k*S; 		for(i=0;i<c;++i){ 			j=(q+p[i]-1)/p[i];j=(j>1?j:2)*p[i]-q; 			for(;j<S;j+=p[i])b[id][j]=1; 		} 		if(!k)b[id][0]=b[id][1]=1; 		for(i=std::max(0,s-q);i<S&&q+i<=e;++i)if(!b[id][i])A[id]+=q+i; 	} 	return 0; } int main(){ 	int n,i,q,j; 	std::cin>>n; 	i=(n-1)/(1<<28);s=i*(1<<28)+2;e=(i+1)*(1<<28); 	if(n-s-1<e-n)R=P[i],e=n;else s=n+1,R=-P[i+1]; 	B=s/S;q=(int)sqrt(e+.0);p[c++]=2; 	for(i=3;i<=q;i+=2)if(!np[i])for(j=i*i,p[c++]=i;j<=q;j+=i)np[j]=1;  	pthread_t t[T]; 	for(i=0;i<T;++i)pthread_create(t+i,0,f,(void*)(i)); 	for(i=0;i<T;++i)pthread_join(t[i],0),R+=A[i]; 	std::cout<<(R>0?R:-R); }  

//@ripatti //идея - блочное решето с предпросчетом ответов для нескольких первых блоков #include <iostream> #include <memory.h> #define S 150000 bool F[40000],B[S]; int P[10000],p=0; long long pre[]={0,79835127420606,307011790722811,675490692294675, 1182357709860117,1825666731904492,2603717273255596,3515373254256955, 4559774703609068,5736228298250417,7043215380181465,8481171232603598, 10049045128993920,11745741297705187,13571569117886223,15525668198679060, 17608378509778587,19817357312226874,22154562782502270,24618987306923167, 27209541722648039}; int main(){ 	int a,b,c,n,Z=(1<<15),Q=S*350; 	std::cin >> n; 	long long ans=pre[n/Q]; 	for(a=2;a*a<Z;a++)if(!F[a])for(b=a*a;b<Z;b+=a)F[b]=true; 	for(a=2;a<Z;a++)if(!F[a])P[p++]=a; 	for(a=(n/Q)*Q;a<=n;a+=S){ 		memset(B,0,sizeof B); 		for(b=0;b<p;b++)for(c=std::max(2,(a+P[b]-1)/P[b])*P[b]-a;c<S;c+=P[b])B[c]=true; 		if(a==0)B[0]=B[1]=true; 		for(b=0;b<S&&a+b<=n;b++)if(!B[b])ans+=a+b; 	} 	std::cout << ans; 	return 0; }

//@kbxxi #include <iostream> long long A[]={0,72619548630277,279209790387276,614333144695291,1075207199997334,1660170771905893,2367646772295462, 3196703482711201,4146437503168147,5215984059716389,6404774487532576,7711724083073573,9137303389808024, 10680189372387880,12340337443955708,14116726304047228,16010026481858292,18019518580817005,20143329357815162, 22383876593236984,24739512092254535,27209541722648039}; char S[50000100]; int p[50100],C,i,j,B=50000000,l,r; long long R=0;     int main(){     	std::cin >> r;        for (i=2;i<=100000;i++)     if (!S[i]){         p[C++]=i;                 for (j=2*i;j<=100000;j+=i)             S[j]=1;     } else S[i]=0;     	l=r/B*B+1; 	for (i=1;p[i]*p[i]<=r;i++){         int v=p[i],P=l/v*v;                 if (P<l) P+=v; 		if (P==v) P+=v; 		if (!(P&1)) P+=v; 		v*=2;         while (P<=r) S[P-l]=1,P+=v;             }     for (i=l;i<=r;i+=2) if (!S[i-l] && i!=1) R+=i; 	if (l==1 && r>1) R+=2;     std::cout<<A[r/B]+R;	 	return 0; }

//@singstio #include<iostream> #include<vector> #include<math.h> using namespace std; int main() {   __int64_t n,sum=0,i,j,sn;   cin>>n;   sn=int(sqrt(n))+1;   vector<bool> s(n+1,true);   for(i=2;i<=sn;i++)     if(s[i]){       for(j=i*i;j<=n;j+=i)s[j]=false;}   for(i=2;i<=n;i++)if(s[i])sum+=i;   cout<<sum<<endl; }