1 /// 2 /// @file phi_tiny.cpp 3 /// @brief Test the partial sieve function phi_tiny(x, a) 4 /// which counts the numbers <= x that are not divisible 5 /// by any of the first a primes with a <= 8. 6 /// 7 /// Copyright (C) 2021 Kim Walisch, <kim.walisch@gmail.com> 8 /// 9 /// This file is distributed under the BSD License. See the COPYING 10 /// file in the top level directory. 11 /// 12 13 #include <PhiTiny.hpp> 14 #include <generate.hpp> 15 16 #include <stdint.h> 17 #include <iostream> 18 #include <cstdlib> 19 #include <vector> 20 #include <random> 21 22 using std::size_t; 23 using namespace primecount; 24 check(bool OK)25void check(bool OK) 26 { 27 std::cout << " " << (OK ? "OK" : "ERROR") << "\n"; 28 if (!OK) 29 std::exit(1); 30 } 31 32 // Count the number of unsieved elements count(std::vector<char> & sieve)33int count(std::vector<char>& sieve) 34 { 35 int cnt = 0; 36 37 for (size_t i = 1; i < sieve.size(); i++) 38 cnt += sieve[i]; 39 40 return cnt; 41 } 42 main()43int main() 44 { 45 std::random_device rd; 46 std::mt19937 gen(rd()); 47 std::uniform_int_distribution<int> dist(10000000, 20000000); 48 49 int64_t max_a = PhiTiny::max_a(); 50 int64_t size = dist(gen); 51 int64_t x = size - 1; 52 53 auto primes = generate_n_primes<int>(max_a); 54 std::vector<char> sieve(size, 1); 55 56 for (int a = 1; a <= max_a; a++) 57 { 58 // remove primes[a] and its multiples 59 for (int j = primes[a]; j <= x; j += primes[a]) 60 sieve[j] = 0; 61 62 std::cout << "phi_tiny(" << x << ", " << a << ") = " << phi_tiny(x, a); 63 check(phi_tiny(x, a) == count(sieve)); 64 } 65 66 std::cout << std::endl; 67 std::cout << "All tests passed successfully!" << std::endl; 68 69 return 0; 70 } 71