Не так уж и медленно:
Код:
? default(parisize,10^8)
*** Warning: new stack size = 100000000 (95.367 Mbytes).
? a=vectorsmall(2^22); a[1]=0; n=0; for(i=2,#a, a[i]=isprime(i)+a[i\2]; if(a[i]>n, print1(i,", "); n++));
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119,
time = 1,202 ms.
? default(parisize,5*10^9)\\GP64
*** Warning: new stack size = 5000000000 (4768.372 Mbytes).
? a=vectorsmall(2^28); a[1]=0; n=0; for(i=2,#a, a[i]=isprime(i)+a[i\2]; if(a[i]>n, print1(i,", "); n++));
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 1min, 14,022 ms.
? default(parisize,10^8)
*** Warning: new stack size = 100000000 (95.367 Mbytes).
? a(n)=if(n<=#v,v[n], isprime(n)+a(n\2));\\n>1!
? v=vectorsmall(16*10^6); v[1]=0; for(i=2,#v, v[i]=isprime(i)+v[i\2]);
time = 3,714 ms.
? n=1; forprime(k=2,2*10^8, if(a(k)!=n, next); print1(k,", "); n++);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 20,124 ms.
? n=1; p=1; forprime(k=2,2*10^8, if(k<p || a(k)!=n, next); print1(k,", "); n++; p=2*k);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 14,867 ms.
? n=1; p=1; forprime(k=2,2*10^8, if(k<p || a(k\2)!=n-1, next); print1(k,", "); n++; p=2*k);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 7,646 ms.
? default(parisize,5*10^9)\\GP64
*** Warning: new stack size = 5000000000 (4768.372 Mbytes).
? a(n)=if(n<=#v,v[n], isprime(n)+a(n\2));\\n>1!
? v=vectorsmall(5*10^8); v[1]=0; for(i=2,#v, v[i]=isprime(i)+v[i\2]);
time = 1min, 57,406 ms.
? n=1; forprime(k=2,2*10^8, if(a(k)!=n, next); print1(k,", "); n++);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 3,198 ms.
? n=1; forprime(k=2,oo, if(a(k)!=n, next); print1(k,", "); n++; if(n>17, break));
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127, 1509921587,
time = 1min, 22,181 ms.
-- 26.11.2021, 16:23 --Иллюстрация насколько к PARI/GP неприменимы обычные методы оптимизации, в данном случае исключение хвостовой рекурсии:
Код:
? default(parisize,10^8)
*** Warning: new stack size = 100000000 (95.367 Mbytes).
? v=vectorsmall(16*10^6); v[1]=0; for(i=2,#v, v[i]=isprime(i)+v[i\2]);
time = 3,714 ms.
? a(n)=if(n<=#v,v[n], isprime(n)+a(n\2));
? n=1; p=1; forprime(k=2,2*10^8, if(k<p || a(k\2)!=n-1, next); print1(k,", "); n++; p=2*k);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 8,002 ms.
? a(n)=my(x=0); while(n>#v, x+=isprime(n); n=n\2); x+v[n];
? n=1; p=1; forprime(k=2,2*10^8, if(k<p || a(k\2)!=n-1, next); print1(k,", "); n++; p=2*k);
2, 5, 11, 23, 47, 191, 383, 1439, 2879, 11519, 23039, 368633, 1474559, 2949119, 47161343, 194224127,
time = 30,749 ms.