1 ///
2 /// @file   generate_lpf.cpp
3 /// @brief  Test least prime factor function
4 ///
5 /// Copyright (C) 2017 Kim Walisch, <kim.walisch@gmail.com>
6 ///
7 /// This file is distributed under the BSD License. See the COPYING
8 /// file in the top level directory.
9 ///
10 
11 #include <generate.hpp>
12 #include <imath.hpp>
13 
14 #include <stdint.h>
15 #include <iostream>
16 #include <cstdlib>
17 #include <vector>
18 #include <random>
19 
20 using namespace primecount;
21 
check(bool OK)22 void check(bool OK)
23 {
24   std::cout << "   " << (OK ? "OK" : "ERROR") << "\n";
25   if (!OK)
26     std::exit(1);
27 }
28 
main()29 int main()
30 {
31   std::random_device rd;
32   std::mt19937 gen(rd());
33   std::uniform_int_distribution<int> dist(200000, 300000);
34 
35   auto max = dist(gen);
36   auto lpf = generate_lpf(max);
37   auto primes = generate_primes<int>(max);
38 
39   for (int i = 2; i <= max; i++)
40   {
41     int factor = i;
42     int sqrt = isqrt(i);
43 
44     // find smallest prime factor
45     for (int j = 1; primes[j] <= sqrt; j++)
46     {
47       if (i % primes[j] == 0)
48       {
49         factor = primes[j];
50         break;
51       }
52     }
53 
54     std::cout << "lpf(" << i << ") = " << lpf[i];
55     check(lpf[i] == factor);
56   }
57 
58   std::cout << std::endl;
59   std::cout << "All tests passed successfully!" << std::endl;
60 
61   return 0;
62 }
63