Rosetta Code

Largest number divisible by its digits: Difference between revisions

Page Discussion

Largest number divisible by its digits (view source)

Revision as of 17:52, 3 December 2022

528 bytes added ,  1 year ago
m
→‎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 lcmlcmd(intlong ax, int b) { return (a * b) / gcd(a,b); }
 
static int lcms(int x) { int r = 2; for (int)(x i% =b), 3a; ix </= xb; i++)while r(x => lcm(r, i0); return r; }{
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 = 98764321, skip = lcms(9)987654321; // 5,all i;digits boolexcept bail;zero
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
bailnDup = falsetrue; // checking for duplicate digits or digit five
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k] || s[k] == '5') { bailnDup = truefalse; break; }
if (!bailnDup) break; } sw.Stop(); // found it
Console.Write("base 10 = {0} in {1} msμs\n", i, sw.Elapsed.TotalMilliseconds);▼
}
1000 * sw.Stop(Elapsed.TotalMilliseconds);
▲ Console.Write("base 10 = {0} in {1} ms\n", i, sw.Elapsed.TotalMilliseconds);
sw.Restart();
mx = 0xfedcba987654321; skip = lcms( // all 15); digits used, no zero
skip = lcmd(mx >> 4, 16); // digit one implied, so omit it
for (i = mx - mx % skip; ; i -= skip) {
var s = i.ToString("Xx").ToCharArray(); Array.Sort(s);
if (s[0] == '0') continue; // no zeros
bailnDup = falsetrue; // checking for duplicate digits
for (int j = 0, k = 1; k < s.Length; j = k++)
if (s[j] == s[k]) { bailnDup = truefalse; break; }
if (!bailnDup) break; } sw.Stop(); // found it
Console.Write("base 16 = {0} in {1} ms", i.ToString("x"), sw.Elapsed.TotalMilliseconds);▼
}
sw.Stop(Elapsed.TotalMilliseconds); } }</syntaxhighlight>
▲ Console.Write("base 16 = {0} in {1} ms", i.ToString("x"), sw.Elapsed.TotalMilliseconds);
}
}</syntaxhighlight>
{{out}}Timing from Tio.run:
<pre>base 10 = 9867312 in 30349.39091 msμs
base 16 = fedcb59726a1348 in 310291.11596791 ms</pre>
 
=== Base 10 only, using Linq ===
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/334062"