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)22void check(bool OK) 23 { 24 std::cout << " " << (OK ? "OK" : "ERROR") << "\n"; 25 if (!OK) 26 std::exit(1); 27 } 28 main()29int 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