Deceptive numbers: Difference between revisions
Content added Content deleted
(→UNIX Shell: make it work with zsh's native operator precedence, too) |
m (Minor code improvement.) |
||
| Line 354: | Line 354: | ||
#include <iostream> |
#include <iostream> |
||
uint64_t power_modulus(uint64_t base, uint64_t exponent, uint64_t modulus) { |
uint64_t power_modulus(uint64_t base, uint64_t exponent, const uint64_t& modulus) { |
||
if ( modulus == 1 ) { |
if ( modulus == 1 ) { |
||
return 0; |
return 0; |
||
| Line 362: | Line 362: | ||
uint64_t result = 1; |
uint64_t result = 1; |
||
while ( exponent > 0 ) { |
while ( exponent > 0 ) { |
||
if ( ( exponent |
if ( ( exponent & 1 ) == 1 ) { |
||
result = ( result * base ) % modulus; |
result = ( result * base ) % modulus; |
||
} |
} |
||
| Line 371: | Line 371: | ||
} |
} |
||
bool is_deceptive(uint32_t n) { |
bool is_deceptive(const uint32_t& n) { |
||
if ( n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && power_modulus(10, n - 1, n) == 1 ) { |
if ( n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && power_modulus(10, n - 1, n) == 1 ) { |
||
for ( uint32_t divisor = 7; divisor < sqrt(n); divisor += 6 ) { |
for ( uint32_t divisor = 7; divisor < sqrt(n); divisor += 6 ) { |
||