Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

//@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("%llun",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("%lldn", 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;
}