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)25 void 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)33 int 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()43 int 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