Anonymous user
Largest number divisible by its digits: Difference between revisions
Largest number divisible by its digits (view source)
Revision as of 19:47, 3 February 2021
, 3 years agoChanged algorithm for base 10 and added base 16.
m (Modified comment.) |
(Changed algorithm for base 10 and added base 16.) |
||
Line 1,114:
===Base 10===
This version uses a combination of several algorithms, especially those of the C++ and the Go/Raku versions. But, to get the digits, instead of converting the number to a string it uses an iterator which is significantly faster. And to check digit uniqueness, it uses a very efficient bit set. The programs runs in less than 20ms.
<lang nim>iterator digits(n: int): int =▼
<lang nim>type Digit = range[0..9]
var n = n
while true:
Line 1,122 ⟶ 1,125:
if n == 0: break
for d in num.digits:
if d == 0 or num mod d != 0 or d in hSet:
hSet.incl(d)
return true
const
func checkDec(num: int): bool =▼
Magic = 9 * 8 * 7
▲ var hSet: set[range[0..9]]
High = 0x9876432 div Magic * Magic
if n.isLynchBell:
break</lang>
{{out}}
<pre>9867312</pre>
===Base 16===
This is the same algorithm adapted for base 16. The program runs in about 30ms.
<lang Nim>import strformat
type Digit = range[0..15]
iterator digits(n: int64): Digit =
var n = n
while true:
yield n and 15
n = n shr 4
if n == 0: break
var hSet: set[Digit]
for d in num.digits:
▲ if firstDigit and d.isOdd: return false
if d == 0 or num mod d != 0 or d in hSet:
return false
Line 1,135 ⟶ 1,167:
return true
const Magic = 15 * 14 * 13 * 12 * 11
▲for i in countdown(98764321, 1):
const High = 0xfedcba987654321 div Magic * Magic
▲ echo i
for n in countdown(High, Magic, Magic):
if n.isLynchBell:
echo &"{n:x}"
break</lang>
{{out}}
<pre>fedcb59726a1348</pre>
=={{header|Perl}}==
| |||