#include <cstddef>
#include <iostream>
template<bool b>
constexpr std::size_t dbg(std::size_t in) {
return b?((std::cout << in << ","), void(), in):in;
}
template<bool b>
constexpr bool dbg_ln(bool in) {
return b?((std::cout << in << ")\n"), void(), in):in;
}
template<bool b>
constexpr std::size_t dbg_start(std::size_t in) {
return b?((std::cout << "(start:" << in << ","), void(), in):in;
}
template<bool b>
constexpr std::size_t dbg_target(std::size_t in) {
return b?((std::cout << "target:" << in << ","), void(), in):in;
}
template<bool b>
constexpr std::size_t dbg_step(std::size_t in) {
return b?((std::cout << "step:" << in << ","), void(), in):in;
}
template<bool b>
constexpr bool dbg_rec(bool in) {
return b?((std::cout << "rec:" << in << ","), void(), in):in;
}
template<bool b>
constexpr bool dbg_check(bool in) {
return b?((std::cout << "chk:" << in << ","), void(), in):in;
}
template<bool debug>
constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step ) {
return dbg_ln<debug>(
!(dbg_start<debug>(start)*start*36 > dbg_target<debug>(target))
&&
(
( (dbg_step<debug>(step)==1)
&& (
dbg_check<debug>(target%(start*6+1) == 0)
|| dbg_check<debug>(target%(start*6+5) == 0)
)
)
||
( (dbg_step<debug>(step) > 1)
&&
(
dbg_rec<debug>(any_factors<debug>( target, start, step/2 ))
|| dbg_rec<debug>(any_factors<debug>( target, start+step/2, step/2 ))
)
)
));
}
template<bool debug>
constexpr bool is_prime_( std::size_t target ) {
// handle 2, 3 and 5:
return
target == 2 || target == 3 || target == 5 ||
(
target%2 != 0
&& target%3 != 0
&& target%5 != 0
&& !any_factors<debug>( target, 1, target/6 + 1 )
); // can make that upper bound a bit tighter, but I don't care
}
constexpr bool is_prime( std::size_t target ) {
return is_prime_<false>(target);
}
constexpr bool is_prime_dbg( std::size_t target ) {
return is_prime_<true>(target);
}
int main() {
// 100103
std::cout << "5:" << is_prime(5) << "\n";
std::cout << "10:" << is_prime(10) << "\n";
std::cout << "13:" << is_prime(13) << "\n";
std::cout << "91:" << is_prime(91) << "\n";
std::cout << "97:" << is_prime(97) << "\n";
std::cout << "100103:" << is_prime(100103) << "\n";
}
I2luY2x1ZGUgPGNzdGRkZWY+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnRlbXBsYXRlPGJvb2wgYj4KY29uc3RleHByIHN0ZDo6c2l6ZV90IGRiZyhzdGQ6OnNpemVfdCBpbikgewogICAgcmV0dXJuIGI/KChzdGQ6OmNvdXQgPDwgaW4gPDwgIiwiKSwgdm9pZCgpLCBpbik6aW47Cn0KdGVtcGxhdGU8Ym9vbCBiPgpjb25zdGV4cHIgYm9vbCBkYmdfbG4oYm9vbCBpbikgewogICAgcmV0dXJuIGI/KChzdGQ6OmNvdXQgPDwgaW4gPDwgIilcbiIpLCB2b2lkKCksIGluKTppbjsKfQp0ZW1wbGF0ZTxib29sIGI+CmNvbnN0ZXhwciBzdGQ6OnNpemVfdCBkYmdfc3RhcnQoc3RkOjpzaXplX3QgaW4pIHsKICAgIHJldHVybiBiPygoc3RkOjpjb3V0IDw8ICIoc3RhcnQ6IiA8PCBpbiA8PCAiLCIpLCB2b2lkKCksIGluKTppbjsKfQp0ZW1wbGF0ZTxib29sIGI+CmNvbnN0ZXhwciBzdGQ6OnNpemVfdCBkYmdfdGFyZ2V0KHN0ZDo6c2l6ZV90IGluKSB7CiAgICByZXR1cm4gYj8oKHN0ZDo6Y291dCA8PCAidGFyZ2V0OiIgPDwgaW4gPDwgIiwiKSwgdm9pZCgpLCBpbik6aW47Cn0KdGVtcGxhdGU8Ym9vbCBiPgpjb25zdGV4cHIgc3RkOjpzaXplX3QgZGJnX3N0ZXAoc3RkOjpzaXplX3QgaW4pIHsKICAgIHJldHVybiBiPygoc3RkOjpjb3V0IDw8ICJzdGVwOiIgPDwgaW4gPDwgIiwiKSwgdm9pZCgpLCBpbik6aW47Cn0KdGVtcGxhdGU8Ym9vbCBiPgpjb25zdGV4cHIgYm9vbCBkYmdfcmVjKGJvb2wgaW4pIHsKICAgIHJldHVybiBiPygoc3RkOjpjb3V0IDw8ICJyZWM6IiA8PCBpbiA8PCAiLCIpLCB2b2lkKCksIGluKTppbjsKfQp0ZW1wbGF0ZTxib29sIGI+CmNvbnN0ZXhwciBib29sIGRiZ19jaGVjayhib29sIGluKSB7CiAgICByZXR1cm4gYj8oKHN0ZDo6Y291dCA8PCAiY2hrOiIgPDwgaW4gPDwgIiwiKSwgdm9pZCgpLCBpbik6aW47Cn0KdGVtcGxhdGU8Ym9vbCBkZWJ1Zz4KY29uc3RleHByIGJvb2wgYW55X2ZhY3RvcnMoIHN0ZDo6c2l6ZV90IHRhcmdldCwgc3RkOjpzaXplX3Qgc3RhcnQsIHN0ZDo6c2l6ZV90IHN0ZXAgKSB7CiAgcmV0dXJuIGRiZ19sbjxkZWJ1Zz4oCiAgICAgICEoZGJnX3N0YXJ0PGRlYnVnPihzdGFydCkqc3RhcnQqMzYgPiBkYmdfdGFyZ2V0PGRlYnVnPih0YXJnZXQpKQogICYmCiAgKAogICAgKCAoZGJnX3N0ZXA8ZGVidWc+KHN0ZXApPT0xKQogICAgICAmJiAoCiAgICAgICAgZGJnX2NoZWNrPGRlYnVnPih0YXJnZXQlKHN0YXJ0KjYrMSkgPT0gMCkKICAgICAgICB8fCBkYmdfY2hlY2s8ZGVidWc+KHRhcmdldCUoc3RhcnQqNis1KSA9PSAwKQogICAgICApCiAgICApCiAgICB8fAogICAgKCAoZGJnX3N0ZXA8ZGVidWc+KHN0ZXApID4gMSkKICAgICAgJiYKICAgICAgKAogICAgICAgIGRiZ19yZWM8ZGVidWc+KGFueV9mYWN0b3JzPGRlYnVnPiggdGFyZ2V0LCBzdGFydCwgc3RlcC8yICkpCiAgICAgICAgfHwgZGJnX3JlYzxkZWJ1Zz4oYW55X2ZhY3RvcnM8ZGVidWc+KCB0YXJnZXQsIHN0YXJ0K3N0ZXAvMiwgc3RlcC8yICkpCiAgICAgICkKICAgICkKICApKTsKfQp0ZW1wbGF0ZTxib29sIGRlYnVnPgpjb25zdGV4cHIgYm9vbCBpc19wcmltZV8oIHN0ZDo6c2l6ZV90IHRhcmdldCApIHsKICAvLyBoYW5kbGUgMiwgMyBhbmQgNToKICByZXR1cm4gCiAgICB0YXJnZXQgPT0gMiB8fCB0YXJnZXQgPT0gMyB8fCB0YXJnZXQgPT0gNSB8fAogICAgKAogICAgICB0YXJnZXQlMiAhPSAwCiAgICAgICYmIHRhcmdldCUzICE9IDAKICAgICAgJiYgdGFyZ2V0JTUgIT0gMAogICAgICAmJiAhYW55X2ZhY3RvcnM8ZGVidWc+KCB0YXJnZXQsIDEsIHRhcmdldC82ICsgMSApCiAgICApOyAvLyBjYW4gbWFrZSB0aGF0IHVwcGVyIGJvdW5kIGEgYml0IHRpZ2h0ZXIsIGJ1dCBJIGRvbid0IGNhcmUKfQpjb25zdGV4cHIgYm9vbCBpc19wcmltZSggc3RkOjpzaXplX3QgdGFyZ2V0ICkgewogICAgcmV0dXJuIGlzX3ByaW1lXzxmYWxzZT4odGFyZ2V0KTsKfQpjb25zdGV4cHIgYm9vbCBpc19wcmltZV9kYmcoIHN0ZDo6c2l6ZV90IHRhcmdldCApIHsKICAgIHJldHVybiBpc19wcmltZV88dHJ1ZT4odGFyZ2V0KTsKfQppbnQgbWFpbigpIHsKICAgIC8vIDEwMDEwMyAKICAgIHN0ZDo6Y291dCA8PCAiNToiIDw8IGlzX3ByaW1lKDUpIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIjEwOiIgPDwgaXNfcHJpbWUoMTApIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIjEzOiIgPDwgaXNfcHJpbWUoMTMpIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIjkxOiIgPDwgaXNfcHJpbWUoOTEpIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIjk3OiIgPDwgaXNfcHJpbWUoOTcpIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIjEwMDEwMzoiIDw8IGlzX3ByaW1lKDEwMDEwMykgPDwgIlxuIjsKfQ==