#include #include #include #include const uint16_t sieve[] = { 2, 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 8, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 8, 4, 2, 6, 4, 6, 12, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 8, 4, 6, 8, 10, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 14, 4, 2, 4, 6, 6, 2, 6, 4, 8, 10, 8, 4, 2, 4, 6, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2, 6, 4, 8, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 6, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 12, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 6, 10, 6, 8, 4, 2, 4, 2, 4, 8, 6, 12, 4, 6, 2, 12, 4, 2, 4, 6, 8, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 8, 6, 4, 2, 10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 4, 2, 12, 10, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 12, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 12, 2, 6, 4, 2, 4, 6, 6, 2, 12, 6, 4, 18, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 14, 10, 2, 4, 2, 4, 6, 2, 6, 10, 6, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 10, 6, 6, 2, 6, 4, 2, 4, 2, 10, 2, 12, 4, 6, 6, 2, 12, 4, 6, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 6, 10, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 8, 4, 8, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 14, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 8, 4, 8, 6, 10, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 6, 6, 10, 8, 4, 2, 4, 6, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 12, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 12, 2, 4, 2, 4, 6, 2, 6, 4, 2, 16, 2, 6, 4, 2, 10, 6, 8, 4, 2, 4, 2, 12, 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 12, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 10, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 6, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 8, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 6, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 6, 8, 6, 10, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 6, 4, 6, 8, 4, 6, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 10, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 12, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4, 2, 10, 2, 12, 6, 4, 6, 2, 10, 2, 4, 6, 6, 8, 4, 2, 6, 18, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 6, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 12, 6, 2, 6, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 10, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 14, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 10, 2, 4, 2, 10, 2, 10, 6, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 6, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 10, 14, 4, 2, 4, 2, 4, 8, 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 14, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 12, 2, 4, 2, 12, 10, 2, 4, 2, 10, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 4, 6, 8, 16, 2, 4, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 16, 2, 6, 4, 8, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 6, 4, 8, 6, 4, 6, 2, 4, 14, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 6, 6, 2, 6, 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 6, 4, 6, 2, 6, 6, 4, 6, 6, 12, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 8, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 10, 2, 6, 6, 4, 6, 6, 8, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 14, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 10, 6, 2, 6, 10, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 12, 4, 2, 4, 8, 6, 6, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 8, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 12, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 8, 4, 2, 4, 6, 6, 2, 10, 2, 6, 18, 4, 2, 4, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 12, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 22, 2, 4, 2, 4, 6, 2, 6, 4, 6, 12, 2, 6, 4, 2, 10, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 6, 12, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 12, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 6, 4, 8, 10, 6, 2, 4, 6, 8, 6, 4, 2, 12, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 8, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10, 6, 2, 6, 4, 2, 4, 6, 6, 8, 6, 6, 10, 12, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 8, 4, 6, 2, 6, 6, 4, 2, 10, 8, 4, 2, 4, 12, 2, 10, 2, 4, 2, 4, 6, 2, 12, 4, 6, 8, 10, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 6, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 10, 2, 12, 4, 6, 8, 6, 4, 2, 4, 2, 10, 2, 16, 2, 4, 6, 2, 10, 2, 4, 6, 6, 2, 6, 4, 2, 10, 14, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 12, 2, 6, 4, 14, 4, 2, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 6, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 8, 10, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 8, 4, 6, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 6, 10, 2, 10, 2, 4, 2, 4, 14, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 6, 6, 2, 6, 6, 4, 12, 2, 6, 4, 2, 10, 6, 8, 4, 2, 6, 4, 8, 6, 10, 2, 4, 6, 14, 4, 2, 10, 2, 6, 4, 2, 4, 2, 12, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 6, 10, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 6, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 8, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 12, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 8, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 4, 6, 8, 6, 6, 6, 4, 6, 12, 6, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 12, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 18, 4, 6, 2, 4, 6, 2, 12, 4, 2, 12, 6, 4, 2, 4, 12, 2, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 6, 10, 12, 6, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 6, 4, 6, 2, 10, 6, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 14, 6, 10, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 6, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 14, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 8, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 10, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 10, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 6, 4, 6, 2, 6, 4, 2, 4, 12, 8, 4, 2, 16, 8, 4, 2, 4, 2, 4, 8, 16, 2, 4, 8, 12, 4, 2, 4, 6, 2, 6, 4, 6, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 10, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 10, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 4, 6, 8, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 14, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 6, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 10, 6, 14, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 6, 10, 2, 6, 4, 6, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 6, 12, 10, 6, 2, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 10, 2, 12, 4, 2, 4, 6, 12, 2, 4, 12, 2, 6, 4, 2, 6, 4, 18, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 12, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 6, 12, 6, 4, 6, 6, 6, 8, 6, 4, 2, 10, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 8, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 12, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 6, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 10, 6, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 6, 2, 10, 2, 4, 14, 6, 4, 2, 10, 6, 8, 4, 6, 2, 4, 8, 6, 10, 2, 4, 6, 2, 12, 4, 6, 6, 2, 6, 6, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 14, 4, 2, 4, 2, 10, 2, 10, 6, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 6, 6, 4, 8, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 10, 6, 2, 10, 8, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 6, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 4, 14, 4, 6, 2, 12, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 14, 10, 2, 4, 6, 2, 6, 6, 4, 2, 10, 2, 6, 4, 2, 16, 2, 10, 2, 4, 2, 4, 6, 8, 6, 4, 12, 2, 10, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 10, 8, 6, 4, 12, 2, 6, 4, 2, 4, 2, 10, 2, 12, 4, 2, 4, 8, 10, 2, 4, 6, 6, 2, 6, 4, 8, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 12, 10, 6, 6, 8, 6, 6, 4, 2, 4, 6, 2, 6, 10, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 8, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 12, 2, 4, 6, 8, 6, 4, 2, 6, 10, 8, 4, 6, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 12, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 12, 6, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 10, 2, 4, 6, 2, 12, 6, 4, 6, 2, 6, 4, 2, 4, 2, 22, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 12, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 6, 4, 2, 4, 18, 6, 2, 10, 2, 6, 6, 4, 2, 4, 8, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 12, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 6, 6, 8, 4, 2, 4, 12, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 8, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 10, 6, 2, 6, 10, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 14, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 12, 2, 10, 2, 4, 2, 4, 8, 6, 6, 4, 6, 6, 2, 10, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 8, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 12, 6, 6, 4, 6, 6, 2, 6, 4, 6, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 6, 6, 2, 6, 6, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 6, 4, 6, 8, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 14, 4, 2, 6, 4, 6, 8, 4, 6, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 8, 4, 6, 2, 16, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 4, 2, 16, 8, 6, 4, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 10, 2, 4, 2, 10, 12, 2, 4, 2, 12, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 14, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 8, 4, 2, 4, 2, 4, 14, 10, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 6, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10, 2, 4, 2, 10, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 14, 4, 2, 4, 8, 10, 6, 2, 4, 6, 2, 6, 10, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 10, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 8, 6, 4, 2, 4, 6, 6, 2, 6, 12, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 6, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 6, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 18, 6, 2, 4, 8, 6, 6, 4, 2, 10, 2, 6, 4, 6, 12, 2, 10, 2, 4, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 12, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 12, 4, 2, 4, 6, 2, 10, 2, 10, 6, 2, 6, 4, 2, 6, 4, 14, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 6, 4, 8, 6, 4, 6, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 10, 6, 8, 6, 4, 2, 12, 6, 4, 6, 6, 6, 2, 6, 6, 6, 4, 6, 2, 6, 6, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 8, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12, 4, 2, 4, 6, 8, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 10, 8, 4, 2, 4, 6, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 10, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 12, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 10, 6, 12, 2, 4, 2, 4, 8, 6, 10, 2, 4, 6, 2, 16, 2, 4, 6, 2, 6, 4, 2, 4, 2, 12, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 8, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 12, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 6, 4, 2, 4, 8, 10, 6, 6, 6, 2, 6, 6, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 10, 6, 8, 4, 8, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 14, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 8, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 10, 6, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 6, 4, 12, 2, 6, 6, 4, 12, 2, 10, 2, 4, 2, 4, 6, 2, 6, 6, 10, 6, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 6, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 10, 2, 6, 6, 10, 6, 2, 6, 4, 2, 4, 2, 10, 14, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 6, 12, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 18, 4, 6, 12, 2, 6, 6, 4, 2, 4, 6, 2, 12, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 12, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 10, 12, 2, 4, 6, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 10, 2, 4, 2, 10, 2, 10, 2, 4, 6, 8, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 4, 8, 6, 4, 2, 4, 12, 2, 6, 4, 12, 6, 8, 4, 2, 4, 2, 4, 8, 6, 10, 6, 6, 2, 12, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 12, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 6, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4, 6, 2, 10, 2, 10, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 6, 4, 2, 4, 8, 10, 8, 4, 6, 2, 6, 6, 4, 2, 4, 14, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 10, 8, 6, 4, 8, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 2, 6, 6, 6, 4, 6, 12, 2, 4, 2, 12, 6, 4, 6, 2, 4, 8, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 8, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 14, 4, 6, 2, 4, 6, 2, 6, 6, 6, 10, 2, 6, 4, 2, 4, 12, 12, 2, 4, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 16, 2, 16 }; const size_t sieve_size = 5767; const size_t sieve_loop = 7; uint64_t isqrt(uint64_t n) { uint64_t x1 = (uint64_t)sqrt((double) n); uint64_t x2 = UINT64_MAX; uint64_t x3 = UINT64_MAX; while (x1 != x3) { x3 = x2; x2 = x1; x1 = (x1 + n / x1) / 2; } return (x1 < x2) ? x1 : x2; } // 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 > 2^64 #define MAX_N_FACTORS 15 typedef struct { int k; uint64_t factors[MAX_N_FACTORS]; int powers[MAX_N_FACTORS]; } Factorization; void factorize(uint64_t n, Factorization *f) { uint64_t sqrt_n = isqrt(n); f->k = 0; size_t i = 0; uint64_t p = 0; for (; ; ) { p += sieve[i]; if (p > sqrt_n) { break; } if (n % p == 0) { f->factors[f->k] = p; f->powers[f->k] = 1; for (; ; ) { n /= p; if (n % p != 0) { break; } ++f->powers[f->k]; } ++f->k; sqrt_n = isqrt(n); } ++i; if (i == sieve_size) { i = sieve_loop; } } if (n > 1) { f->factors[f->k] = n; f->powers[f->k] = 1; ++f->k; } } void print_pairs_iter( uint64_t n, uint64_t sqrt_n, uint64_t q, int k, Factorization *f ) { if (k == 0) { printf("= %" PRIu64 " * %" PRIu64 "\n", q, n / q); return; } print_pairs_iter(n, sqrt_n, q, k - 1, f); for (int i = 0; i < f->powers[k - 1]; ++i) { q *= f->factors[k - 1]; if (q > sqrt_n) { break; } print_pairs_iter(n, sqrt_n, q, k - 1, f); } } void print_pairs(uint64_t n, Factorization *f) { print_pairs_iter(n, isqrt(n), 1, f->k, f); } void print_factorization(uint64_t n) { Factorization f; printf("\n%" PRIu64 " =\n", n); factorize(n, &f); print_pairs(n, &f); } void help(const char *name) { fprintf(stderr, "Usage: %s FIRST LAST REPEAT\n", name); exit(1); } int main(int argc, char **argv) { if (argc < 2 || 4 < argc) { help(argv[0]); } uint64_t first; if (sscanf(argv[1], "%" SCNu64, &first) != 1) { help(argv[0]); } uint64_t last = first; if (argc >= 3) { if (sscanf(argv[2], "%" SCNu64, &last) != 1) { help(argv[0]); } } unsigned repeat = 1; if (argc >= 4) { if (sscanf(argv[3], "%u", &repeat) != 1) { help(argv[0]); } } if (first <= last) { for (unsigned k = 0; k < repeat; ++k) { for (uint64_t n = first; n < last; ++n) { print_factorization(n); } print_factorization(last); } } }