diff options
| author | mzuenni <mzuenni@users.noreply.github.com> | 2024-07-28 22:54:40 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-07-28 22:54:40 +0200 |
| commit | 8d11c6c8213f46f0fa19826917c255edd5d43cb1 (patch) | |
| tree | 96d75baff33d5a04b5a60f1a41f514a26c716874 /content/math/piLehmer.cpp | |
| parent | 8c33b4e0d3030cfed17fc64b4fe41133339f6d87 (diff) | |
Test (#4)
* update
* moved content in subdir
* rename file
* add test setup
* add test setup
* add github action
* automaticly test all cpp files
* timeout after 10s
* setulimit and dont zero memory
* test build pdf
* install latexmk
* update
* update
* ngerman
* fonts
* removed old code
* add first test
* added tests
* test in sorted order
* more tests
* simplified test
* more tests
* fix suffix tree
* fixes and improvements
* done ust lst directly
* fix swap
* add links to pdf
* fix constants
* add primorial
* add comment
* various improvements
* more tests
* added missing stuf
* more tests
* fix tests
* more tests
* more tests
* more tests
* fix recursion?
* test trie
* more tests
* only use python temporarily for listings
* only use python temporarily for listings
* more tests
* fix longestCommonSubstring
* more tests
* more tests
* made code more similiar
* fix?
* more tests
* more tests
* more tests
* add ahoCorasick test + limit 4GB stack size
* more tests
* fix test
* add additional test
* more tests
* more tests
* fix?
* better fix
* fix virtual tree
* more tests
* more tests
* recursive closest pair
* more tests
* decrease limit
* new tests
* more tests
* fix name
* more tests
* add test
* new test
* more tests
* more tests
* more tests
* more tests
* new test and content
* new code
* new code
* larger tests
* fix and test
* new test
* new test
* update pdf
* remove comments
* new test
* more tests
* more testcases
* more tests
* increased limit
* more tests
* more tests
* more tests
* new tests
* more tests
* shortened code
* new test
* add basic tests for bigint
* more tests
* removed old files
* new test
* ignore some files
* more auto more ccw
* fix test
* more tests
* fix
* new tests
* more tests
* more tests
* stronger test
* actually verify delaunay...
* more tests
* fix header
* more tests
* run tests parallel?
* test parralel?
* add --missing
* separate workflows
* test
* is the pdf checked?
* separate workflows
* fix workflow
* more workflows
---------
Co-authored-by: Yidi <noob999noob999@gmail.com>
Diffstat (limited to 'content/math/piLehmer.cpp')
| -rw-r--r-- | content/math/piLehmer.cpp | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp new file mode 100644 index 0000000..17df85e --- /dev/null +++ b/content/math/piLehmer.cpp @@ -0,0 +1,52 @@ +constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17;
+constexpr ll cacheB = 7;
+ll memoA[cacheA + 1][cacheB + 1];
+ll memoB[cacheB + 1];
+ll memoC[N];
+
+void init() {
+ primeSieve(); // @\sourceref{math/primeSieve.cpp}@
+ for (ll i = 0; i < N; i++) {
+ memoC[i] = memoC[i - 1];
+ if (isPrime(i)) memoC[i]++;
+ }
+ memoB[0] = 1;
+ for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i;
+ for(ll i = 1; i <= cacheB; i++) {
+ memoB[i] = primes[i - 1] * memoB[i - 1];
+ for(ll j = 1; j <= cacheA; j++) {
+ memoA[j][i] = memoA[j][i - 1] - memoA[j /
+ primes[i - 1]][i - 1];
+}}}
+
+ll phi(ll n, ll k) {
+ if(k == 0) return n;
+ if(k <= cacheB)
+ return memoA[n % memoB[k]][k] +
+ (n / memoB[k]) * memoA[memoB[k]][k];
+ if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1;
+ if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) {
+ ll b = memoC[(ll)sqrtl(n)];
+ ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2;
+ for(ll i = k; i < b; i++) res += memoC[n / primes[i]];
+ return res;
+ }
+ return phi(n, k - 1) - phi(n / primes[k - 1], k - 1);
+}
+
+ll pi(ll n) {
+ if (n < N) return memoC[n];
+ ll a = pi(sqrtl(sqrtl(n)));
+ ll b = pi(sqrtl(n));
+ ll c = pi(cbrtl(n));
+ ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2;
+ for (ll i = a; i < b; i++) {
+ ll w = n / primes[i];
+ res -= pi(w);
+ if (i > c) continue;
+ ll bi = pi(sqrtl(w));
+ for (ll j = i; j < bi; j++) {
+ res -= pi(w / primes[j]) - j;
+ }}
+ return res;
+}
|