85Smith
- Check
- 13 = 5 + 8
Check Smith Number in C#
What you’ll learn
- Smith number rule: composite and
S(n) == F(n). - How to compute digit sum of a number and of its prime factors.
- Why prime numbers are excluded from the Smith definition.
- Range checking, live preview, and interview edge cases.
Overview
A Smith number is composite and has equal digit sums between the number and its prime factorization (with multiplicity). Example: 85 has digit sum 8+5=13, and factors 5 × 17 give 5 + (1+7)=13.
Two C# examples
Check one number and list Smith numbers up to 100.
Live preview
See both sums and the composite rule in one output.
Correct definition
Prime numbers are excluded even if digit sums match.
Prerequisites
Prime/composite basics, digit-sum function, and trial-division factorization.
- Understand factor multiplicity (repeated primes count repeatedly).
- Use integer loops safely with
i <= x / i.
Understanding the concept of Smith numbers
A Smith number is a composite number whose own digit sum equals the digit sum of its prime factors (including repeated factors).
Examples include 4, 22, 27, 85. Primes are excluded by definition even if their digit sums would match trivially.
Math note
Let S(n) be the sum of digits of n, and F(n) be the sum of digits of prime factors with multiplicity. The Smith condition is S(n) = F(n) with n composite.
Example
27 = 3 × 3 × 3 → S(27)=9, F(27)=3+3+3=9.
Quick examples
27Smith
- Factors
- 3 × 3 × 3
7Not
- Reason
- Prime (excluded)
Live preview
Trial factorization in the browser using the same logic as the C# code.
Algorithm
Goal: decide if integer n is a Smith number.
Reject invalids
If n <= 1 or prime, return false.
Compute sums
Compute S(n) and factor-digit sum F(n).
Compare
If S(n) == F(n), it is Smith.
📜 Pseudocode
Pseudocode
function isSmith(n):
if n <= 1 or isPrime(n):
return false
s = digitSum(n)
f = factorDigitSum(n)
return s == f1
Check one number
Reference program: tests whether 85 is a Smith number with composite guard and sqrt-bounded factorization.
c#
using System;
class Program
{
static int DigitSum(int n)
{
int sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
static bool IsPrime(int n)
{
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= n / i; i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
static int FactorDigitSum(int n)
{
int sum = 0;
int x = n;
for (int i = 2; i <= x / i; i++)
{
while (x % i == 0)
{
sum += DigitSum(i);
x /= i;
}
}
if (x > 1)
sum += DigitSum(x);
return sum;
}
static bool IsSmithNumber(int n)
{
if (n <= 1 || IsPrime(n))
return false;
return DigitSum(n) == FactorDigitSum(n);
}
static void Main()
{
int number = 85;
if (IsSmithNumber(number))
Console.WriteLine($"{number} is a Smith Number.");
else
Console.WriteLine($"{number} is not a Smith Number.");
}
}2Smith numbers in range
Smith numbers in range 1 to 100
Reuses IsSmithNumber inside a range loop — matches the reference range output.
c#
using System;
class Program
{
static int DigitSum(int n)
{
int sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
static bool IsPrime(int n)
{
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= n / i; i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
static int FactorDigitSum(int n)
{
int sum = 0;
int x = n;
for (int i = 2; i <= x / i; i++)
{
while (x % i == 0)
{
sum += DigitSum(i);
x /= i;
}
}
if (x > 1)
sum += DigitSum(x);
return sum;
}
static bool IsSmithNumber(int n)
{
if (n <= 1 || IsPrime(n))
return false;
return DigitSum(n) == FactorDigitSum(n);
}
static void Main()
{
Console.WriteLine("Smith Numbers in the Range 1 to 100:");
for (int i = 1; i <= 100; i++)
{
if (IsSmithNumber(i))
Console.Write($"{i} ");
}
Console.WriteLine();
}
}Optimization and alternatives
Factorization. Trial division to sqrt(n) is sufficient for interview-size inputs.
Composite guard. Reject primes first so the definition remains correct.
Shared helper. One DigitSum function for both the number and each prime factor.
❓ FAQ
A Smith number is a composite number where the digit sum of n equals the digit sum of its prime factors (counting repeats).
If primes were allowed, every prime would pass trivially, so the standard definition excludes primes.
Yes. 8+5=13 and factors are 5 and 17 whose digit sums are 5 and 8, total 13.
No. 7 is prime, and primes are excluded.
Multiplicity is part of prime factorization; for 27 = 3*3*3, you add the digit sum of 3 three times.
With trial division for factors, one check is typically O(sqrt(n)) time and O(1) extra space.
🔄 Input / output examples
Input n | Result | Why |
|---|---|---|
85 | Smith | 13 = 5 + 8 |
27 | Smith | 9 = 3+3+3 |
7 | Not Smith | Prime (excluded) |
1 | Not Smith | Not composite |
Edge cases and pitfalls
Most bugs come from skipping the composite check or not counting repeated factors.
n = 1Not Smith
It is not composite and should be rejected immediately.
Prime powers
Multiplicity matters
For 27 = 3 × 3 × 3, include the digit sum of 3 three times.
Loop bound
Overflow safety
Prefer i <= x / i over i * i <= x for large values.
⏱️ Time and space complexity
| Step | Time | Extra space |
|---|---|---|
| Prime check | O(√n) | O(1) |
| Factor digit sum | O(√n) | O(1) |
Single IsSmithNumber | O(√n) | O(1) |
Summary
- Definition: composite
nwith matching digit sumsS(n)andF(n). - Code: trial division with multiplicity and prime rejection.
- Known values to 100:
4, 22, 27, 58, 85, 94.
Did you know?
Small Smith numbers are 4, 22, 27, 58, 85, 94. Primes are never Smith numbers by definition.
About the author
9 people found this page helpful