Largest number divisible by its digits: Difference between revisions
Largest number divisible by its digits (view source)
Revision as of 17:52, 3 December 2022
, 1 year ago→Both: more explanation, minor code revision
(→{{header|ALGOL 68}}: Adjust layout to avoid wrapped lines, add parenthesis so it works with Rutgers Algol 68 as well as Algol 68G) |
m (→Both: more explanation, minor code revision) |
||
Line 479:
=== Both ===
Skips unnecessary numbers, sorts the digits of the tested number (which makes it simple to find zeros and repeated digits). Stops as soon as it finds the first (highest) one. Determines the skip amount by finding the least common multiple of the product of the digits utilized. Base 10 uses all digits but digit five and digit zero, base 16 uses all digits but digit zero. Note that digit five is omitted in base 10 because it would eliminate the even numbers. The eight digits remaining cannot be evenly divided by three, so the base 10 result must have seven digits or less.
<syntaxhighlight lang="csharp">using System;
class Program {
static int gcd(int a, int b) { return b > 0 ? gcd(b, a % b) : a; }
// returns least common multiple of digits of x in base b
static int
r = (r * (a = (int)(x % b))) / gcd(r, a); x /= b; } return r; }
static void Main(string[] args) {
var sw = System.Diagnostics.Stopwatch.StartNew();
long mx =
mx = 98764321; // omitting 5 because even numbers are lost
mx /= 10; // 7 digs because 8 digs won't divide by 3
long skip = lcmd(mx, 10), i; bool nDup;
for (i = mx - mx % skip; ; i -= skip) {
var s = i.ToString().ToCharArray(); Array.Sort(s);
if (s[0] == '0') continue; // no zeros
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k] || s[k] == '5') {
if (
1000 * sw.
▲ Console.Write("base 10 = {0} in {1} ms\n", i, sw.Elapsed.TotalMilliseconds);
sw.Restart();
mx = 0xfedcba987654321;
skip = lcmd(mx >> 4, 16); // digit one implied, so omit it
for (i = mx - mx % skip; ; i -= skip) {
var s = i.ToString("
if (s[0] == '0') continue; // no zeros
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k]) {
if (
sw.
▲ Console.Write("base 16 = {0} in {1} ms", i.ToString("x"), sw.Elapsed.TotalMilliseconds);
{{out}}Timing from Tio.run:
<pre>base 10 = 9867312 in
base 16 = fedcb59726a1348 in
=== Base 10 only, using Linq ===
|