85Smith
- Check
- 13 = 5 + 8
Check Smith Number in Java
What you’ll learn
- Smith number rule: composite and
S(n) == F(n). - How to compute digit sum of a number and factor digits.
- Why prime numbers are excluded from Smith definition.
- Range checking and live preview interpretation.
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 x 17 give 5 + (1+7)=13.
Two Java 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.
What is a Smith number?
A Smith number is a composite number whose own digit sum equals the digit sum of its prime factors (including repeated factors).
Primes are excluded by definition even if their digit sums would match trivially.
Math note
Let S(n) be sum of digits of n, and F(n) be sum of digits of prime factors with multiplicity. Smith condition is S(n) = F(n) with n composite.
Quick examples
27Smith
- Factors
- 3 x 3 x 3
7Not
- Reason
- Prime (excluded)
Live preview
Trial factorization in the browser using the same logic as the Java code.
Algorithm
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
java
public class Main {
static int digitSum(int n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
static boolean 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 boolean isSmith(int n) {
if (n <= 1 || isPrime(n)) return false;
return digitSum(n) == factorDigitSum(n);
}
public static void main(String[] args) {
int number = 85;
if (isSmith(number)) {
System.out.println(number + " is a Smith Number.");
} else {
System.out.println(number + " is not a Smith Number.");
}
}
}2
Smith numbers in range 1 to 100
java
public class Main {
static int digitSum(int n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
static boolean 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 boolean isSmith(int n) {
if (n <= 1 || isPrime(n)) return false;
return digitSum(n) == factorDigitSum(n);
}
public static void main(String[] args) {
System.out.println("Smith Numbers in the Range 1 to 100:");
for (int i = 1; i <= 100; i++) {
if (isSmith(i)) {
System.out.print(i + " ");
}
}
}
}Efficiency notes
Factorization. Trial division to √n is sufficient for interview-size inputs.
Composite guard. Reject primes first so the definition remains correct.
Implementation: use i <= x / i and one shared digit-sum helper.
❓ FAQ
A Smith number is a composite number where digit sum of n equals digit sum of prime factors (counting repeats).
If primes were allowed, every prime would pass trivially, so 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 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 | Output |
|---|---|
85 | Smith number |
27 | Smith number |
7 | Not Smith (prime) |
Edge cases and pitfalls
Most bugs come from skipping composite validation or not counting repeated factors.
n = 1
Not Smith
It is not composite and should be rejected immediately.
Prime powers
Multiplicity matters
For 27 = 3 x 3 x 3, include digit sum of 3 three times.
Overflow safety
Loop bound
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 isSmith | 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