наткнулся тут случайно на задачку по программированию.
Программа должна прочитать из стандартного потока ввода целое число N (от 1 до 2 в 30 степени), и напечатать сумму простых чисел меньших либо равных N.Побеждает тот, кто напишет самое быстрое решение
как бы ничего сложного!
но есть ограничения:
Размер файла с решением — не более 1024 байт (типа 1000 букв)
Допустимое время работы на каждый тест — не более 60 секунд.
понравился комментарий огранизатора -
я хотел рассказать и об алгоритмах решения — но сейчас я вижу, что понятия не имею, как работают первые 2 места
---------- 1 место -------------------
//@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"
-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u;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?0:A+=i+L;printf("%llu\n",A);}
--------- 2 место -----------
//@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=221*a+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);
}
Вот сижу я думаю... толи лыжи не едут...
кароче захотелось напиЦо 
Автор
Тема: Для любознательных (Прочитано 230613 раз)
