A Smith number is a composite integer whose digit sum equals the digit sum of its prime factors with multiplicity.
Remember
n is composite
AND DigitSum(n) == DigitSum of all prime factors (repeats count)
Examples: 4, 22, 27, 58, 85, 94
4 = 2 × 2 → 4 == 2 + 2
85 = 5 × 17 → 8+5 == 5 + (1+7)
27 = 3 × 3 × 3 → 2+7 == 3+3+3
n
Factors
Digit sum
Factor digits
Smith?
4
2 × 2
4
2 + 2 = 4
Yes
85
5 × 17
13
5 + 1 + 7 = 13
Yes
15
3 × 5
6
3 + 5 = 8
No
7
prime
—
—
No
Approach
How to Check a Smith Number in C#
Five clear steps — then reuse the helpers to list Smith numbers in a range.
Reject n ≤ 1 (not composite).
Factorize n with trial division (keep factors with multiplicity).
If only one prime factor appears once, n is prime → not Smith.
Compare DigitSum(n) with the digit sum of every factor.
Equal sums → Smith; otherwise not.
Helper
Job
Time
DigitSum
Sum digits of one integer
O(log n)
Factorize
Collect prime factors with repeats
O(√n)
IsSmith
Composite + matching sums
O(√n)
Pseudocode
Pseudocode
function DigitSum(x):
s = 0
while x > 0:
s = s + (x % 10)
x = x / 10
return s
function IsSmith(n):
if n <= 1: return false
original = n
factorDigitSum = 0
factorCount = 0
// peel off factor 2
while n % 2 == 0:
factorDigitSum = factorDigitSum + DigitSum(2)
factorCount = factorCount + 1
n = n / 2
// odd factors
f = 3
while f * f <= n:
while n % f == 0:
factorDigitSum = factorDigitSum + DigitSum(f)
factorCount = factorCount + 1
n = n / f
f = f + 2
if n > 1: // leftover prime
factorDigitSum = factorDigitSum + DigitSum(n)
factorCount = factorCount + 1
if factorCount == 1: return false // prime
return DigitSum(original) == factorDigitSum
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Rule
Composite and DigitSum(n) == FactorDigitSum
Multiplicity
Count repeated factors (e.g. three 3’s in 27)
Primes
Never Smith
Smallest
4
Classic yes
4, 22, 27, 58, 85, 94
Classic no
1, 7 (prime), 15 (sums differ)
Try it
Live Preview
Enter an integer to factorize it and compare digit sums.
Whole numbers only. Tap a chip or type a value.
Result
n = 85
Factors: 5 × 17
DigitSum(85) = 13
Factor digits = 5 + 1 + 7 = 13
85 is a Smith number
Build DigitSum and IsSmith, then list Smith numbers in a small range.
Example 1 — IsSmith Check
Factorize with multiplicity, reject primes, then compare digit sums.
C#
using System;
class Program
{
static int DigitSum(int x)
{
int s = 0;
while (x > 0)
{
s += x % 10;
x /= 10;
}
return s;
}
static bool IsSmith(int n)
{
if (n <= 1)
{
return false;
}
int original = n;
int factorDigitSum = 0;
int factorCount = 0;
while (n % 2 == 0)
{
factorDigitSum += DigitSum(2);
factorCount++;
n /= 2;
}
for (int f = 3; f * f <= n; f += 2)
{
while (n % f == 0)
{
factorDigitSum += DigitSum(f);
factorCount++;
n /= f;
}
}
if (n > 1)
{
factorDigitSum += DigitSum(n);
factorCount++;
}
if (factorCount == 1)
{
return false; // prime
}
return DigitSum(original) == factorDigitSum;
}
static void Main()
{
int number = 85;
Console.WriteLine(number + (IsSmith(number) ? " is a Smith number" : " is not a Smith number"));
}
}
Output
85 is a Smith number
How It Works
DigitSum peels off each last digit with % 10.
Even factors are peeled with the while (n % 2 == 0) loop.
Odd trial factors continue until f * f > n.
A leftover n > 1 is itself a prime factor.
factorCount == 1 means the original value was prime → reject.
Otherwise compare digit sums; for 85 both sides are 13.
Example 2 — Smith Numbers in a Range
Reuse IsSmith to print every Smith number from 1 to 100.
C#
using System;
class Program
{
static int DigitSum(int x)
{
int s = 0;
while (x > 0)
{
s += x % 10;
x /= 10;
}
return s;
}
static bool IsSmith(int n)
{
if (n <= 1)
{
return false;
}
int original = n;
int factorDigitSum = 0;
int factorCount = 0;
while (n % 2 == 0)
{
factorDigitSum += DigitSum(2);
factorCount++;
n /= 2;
}
for (int f = 3; f * f <= n; f += 2)
{
while (n % f == 0)
{
factorDigitSum += DigitSum(f);
factorCount++;
n /= f;
}
}
if (n > 1)
{
factorDigitSum += DigitSum(n);
factorCount++;
}
if (factorCount == 1)
{
return false;
}
return DigitSum(original) == factorDigitSum;
}
static void Main()
{
int start = 1;
int end = 100;
Console.WriteLine("Smith numbers from " + start + " to " + end + ":");
for (int i = start; i <= end; i++)
{
if (IsSmith(i))
{
Console.Write(i + " ");
}
}
Console.WriteLine();
}
}
Output
Smith numbers from 1 to 100:
4 22 27 58 85 94
How It Works
Same helpers as Example 1 keep the rule in one place.
The outer loop visits every integer from start to end.
Only values that pass IsSmith are printed.
Primes and unmatched composites are skipped automatically.
Up to 100 the classic list is 4 22 27 58 85 94.
Edge Cases & Pitfalls
Check these before calling the solution done.
Primes
Always reject
If factorCount == 1, the number is prime — not Smith.
Repeats
Count multiplicity
For 27, add digit sum of 3 three times.
Multi-digit
Factor digits too
For 17 use 1 + 7, not the bare value 17.
1
Not composite
Return false for n ≤ 1 before factoring.
Analysis
Time and Space Complexity
Program
Time
Extra space
IsSmith (trial factors)
O(√n)
O(1)
Smith in range 1..N
O(N√N)
O(1)
Digit summing is cheap next to factorization. For interview sizes, trial division is enough.
Remember
Key Takeaways
Definition: composite + matching digit sums of number and prime factors.
Multiplicity: repeated factors count every time.
Primes: never Smith — exclude with a factor count of 1.
Test set: 85 → yes; 27 → yes; 15 → no; 7 → no.
One line: if n is composite and its digit sum matches the digit sum of its prime factors, n is Smith.
Frequently Asked Questions
A Smith number is a composite integer whose digit sum equals the digit sum of all its prime factors, counting repeats. Examples: 4, 22, 27, 58, 85, 94.
By definition primes are excluded. Otherwise every prime would pass, because its only prime factor is itself.
Yes. For 27 = 3 × 3 × 3, the factor digit sum is 3 + 3 + 3 = 9, matching 2 + 7.
Yes. 4 = 2 × 2. Digit sum is 4 and factor digit sum is 2 + 2 = 4.
Trial factorization up to √n is O(√n). Listing Smith numbers from 1 to N by checking each value is about O(N√N).
