Kim Walisch kimwalisch
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <primesieve.h> | |
| #include <stdio.h> | |
| int main() | |
| { | |
| primesieve_iterator it; | |
| primesieve_init(&it); | |
| uint64_t prime; | |
| /* iterate over the primes below 10^6 */ |
kimwalisch
/ compile.sh
Last active
August 23, 2016 18:11
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Compile using default C++ compiler | |
| c++ -O2 segmented_sieve.cpp -o segmented_sieve | |
| # Count the primes below 10^9 | |
| time ./segmented_sieve 1000000000 |
kimwalisch
/ primesieve_ checksums.sh
Created
August 23, 2016 19:23
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 45a20e525e3c19fc98e583101af166fd5e6b2324 primesieve-5.7.2.tar.gz | |
| 064b79afeff39866b3c17d390c790778460e5a1c primesieve-5.7.2.zip | |
| 6fd3e6d98a6d4bf7a7234279deaa4eff193235b9 primesieve-5.7.0-win64.zip | |
| c7f3e96c4e1a0e23131f6a39f4086d6d275b0b6c primesieve-5.7.0-win64-console.zip | |
| 8e3f62c850efe591286fcc2262a7f4af4cad285b primesieve-5.5.0-linux-x64.tar.gz | |
| 31215c1dcbc3899f4929b1291a0cb73522111b6d primesieve-5.7.0-linux-x64-console.tar.gz | |
| 4095d6d2f88a71f8bf86cea1332b539025320bec primesieve-5.5.0-macosx-x64.zip | |
| 7ea817d4555dc378e0abf9d14400af8de95dc9f7 primesieve-5.5.0-macosx-x64-console.zip | |
| da7a99173692da005ace827b0df17cb3e7ab1356 primesieve-3.6-win32.zip | |
| 9d16566558aee0b71139f5f95dff23d808d2d886 primesieve-3.6-win32-console.zip |
kimwalisch
/ primesieve_ checksums.sh
Last active
February 11, 2019 09:38
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| e9d01635ae2313ea5d3b5bf2b8c204bac7932c68 primesieve-7.4.zip | |
| 72aa38a72a07a87e5fbf6aa1118fa1b1596a8fef primesieve-7.4.tar.gz | |
| 69f4916e8390a79db443d7842399251a5a54dbb8 primesieve-7.4-win64.zip | |
| d4b88dd6a83c82ac075494458d3c0e4cc19da425 primesieve-7.4-linux-x64.tar.xz | |
| 4095d6d2f88a71f8bf86cea1332b539025320bec primesieve-5.5.0-macOS-x64.zip | |
| 4f04d35d7cdb701ae142f7e286f1641590d9b4b2 primesieve-7.4-win64-console.zip | |
| f4d80d2bfd1d5db3fde4fd50737bf3e0d96e26d3 primesieve-7.4-linux-x64-console.tar.xz | |
| c1c7b6c5f078d51e7e09d67e3e091f3a14610ee3 primesieve-7.4-macOS-x64-console.zip | |
| da7a99173692da005ace827b0df17cb3e7ab1356 primesieve-3.6-win32.zip | |
| 9d16566558aee0b71139f5f95dff23d808d2d886 primesieve-3.6-win32-console.zip |
kimwalisch
/ stars.sh
Created
September 3, 2016 21:02
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/bin/sh | |
| total_stars=0 | |
| for i in {'primesieve','primecount','primesum','calculator'} | |
| do | |
| stars=$(curl --silent "https://api.github.com/repos/kimwalisch/$i" \ | |
| -H 'Accept: application/vnd.github.preview' \ | |
| | grep stargazers_count \ | |
| | cut -f2 -d':' \ |
kimwalisch
/ int128.h
Created
November 22, 2017 12:25
— forked from Bananattack/int128.h
A signed 128-bit integer type. Internally stores its data in Two's Complement within two unsigned 64-bit integer parts. Still needs more testing, but basic implementation is fairly complete.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef WIZ_UTILITY_INT128_H | |
| #define WIZ_UTILITY_INT128_H | |
| #include <cassert> | |
| #include <cstdint> | |
| #include <cstddef> | |
| #include <cstring> | |
| #include <cstdlib> | |
| #include <utility> | |
| #include <string> |
kimwalisch
/ segmented_sieve1.cpp
Last active
March 4, 2018 18:47
Set the segment size in the segmented sieve of Eratosthenes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// Set your CPU's L1 data cache size (in bytes) here | |
| const int64_t L1D_CACHE_SIZE = 32768; | |
| /// Generate primes using the segmented sieve of Eratosthenes. | |
| /// This algorithm uses O(n log log n) operations and O(sqrt(n)) space. | |
| /// @param limit Sieve primes <= limit. | |
| /// | |
| void segmented_sieve(int64_t limit) | |
| { | |
| int64_t sqrt = (int64_t) std::sqrt(limit); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| for (int64_t low = 0; low <= limit; low += segment_size) | |
| { | |
| std::fill(sieve.begin(), sieve.end(), true); | |
| // current segment = [low, high] | |
| int64_t high = low + segment_size - 1; | |
| high = std::min(high, limit); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // generate sieving primes using simple sieve of Eratosthenes | |
| for (; i * i <= high; i += 2) | |
| if (is_prime[i]) | |
| for (int64_t j = i * i; j <= sqrt; j += i) | |
| is_prime[j] = false; | |
| // initialize sieving primes for segmented sieve | |
| for (; s * s <= high; s += 2) | |
| { | |
| if (is_prime[s]) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // sieve the current segment | |
| for (std::size_t i = 0; i < primes.size(); i++) | |
| { | |
| int64_t j = multiples[i]; | |
| for (int64_t k = primes[i] * 2; j < segment_size; j += k) | |
| sieve[j] = false; | |
| multiples[i] = j - segment_size; | |
| } |