Smith Number Program in Java and Python
Smith number program with algorithm, explanation, Java solution and simple Python solution for ICSE and ISC students.
Question:
A Smith number is a composite number whose sum of digits is equal to the sum of the digits of its prime factors, excluding 1. Write a program to input a number and display whether it is a Smith number or not.
Algorithm:
Step 1: Start.
Step 2: Accept number n.
Step 3: Define method sumDig() to return the sum of digits of a number.
Step 4: Define method sumPrimeFact() to calculate the sum of digits of all prime factors.
Step 5: In sumPrimeFact(), start divisor i from 2.
Step 6: While the number is greater than 1, check whether i divides it.
Step 7: If divisible, add sumDig(i) to factor sum and divide the number by i.
Step 8: If not divisible, increase i.
Step 9: Compare the digit sum of the original number with the factor digit sum.
Step 10: Display whether the number is a Smith number.
Step 11: Stop.
Explanation:
The program checks the Smith number condition by calculating two separate sums and comparing them. The first sum is the sum of digits of the original number. The second sum is the sum of digits of all the prime factors of that number. If both sums are equal, the number is a Smith number.
The method sumDig() is used whenever the digit sum of a number is required. It repeatedly extracts the last digit using n % 10, adds it to s, and then removes that digit using n / 10. This method is used once for the original number and also for every factor found during factorisation.
The method sumPrimeFact() performs the prime factorisation. It starts checking from i = 2. If i divides n exactly, then i is treated as a factor at that stage. Its digit sum is added to sum, and n is divided by i. The value of i is not increased immediately after a successful division, because the same factor may occur again. If i does not divide n, the program tries the next possible factor. Finally, a and b are compared to decide the result.
The design of the program is method-based because the same digit-sum logic is needed in more than one place. Instead of repeating that code, sumDig() is called wherever a digit sum is required. The factorisation method works by gradually reducing the original number. When a factor is found, the reduced number is tested again with the same factor, which correctly handles repeated prime factors such as 2 × 2 or 3 × 3. The final comparison is meaningful because both sides represent digit sums: one from the original number and the other from its prime factorisation.
Java Program:
/**
* The class Smith inputs a number and checks whether it is a Smith Number or not
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC Practical 2008 Question 1
*/
import java.util.Scanner;
class Smith
{
// Returns the sum of digits of any number passed to it.
int sumDig(int n)
{
int s = 0;
// Extract and add digits from right to left.
while(n > 0)
{
s = s + n % 10;
n = n / 10;
}
return s;
}
// Returns the sum of digits of all prime factors of the number.
int sumPrimeFact(int n)
{
int i = 2;
int sum = 0;
// Continue until the number has been completely factorised.
while(n > 1)
{
// If i divides n exactly, i is one factor of n.
if(n % i == 0)
{
sum = sum + sumDig(i); // Add digit sum of the current prime factor.
n = n / i; // Remove this factor and test the reduced number again.
}
else
{
i++; // Try the next possible factor.
}
}
return sum;
}
public static void main(String args[])
{
Smith ob = new Smith();
Scanner sc = new Scanner(System.in);
System.out.print("Enter a Number: ");
int n = sc.nextInt();
int a = ob.sumDig(n); // Sum of digits of the original number.
int b = ob.sumPrimeFact(n); // Sum of digits of its prime factors.
System.out.println("Sum of Digit = " + a);
System.out.println("Sum of Prime Factor = " + b);
if(a == b)
System.out.print("It is a Smith Number");
else
System.out.print("It is Not a Smith Number");
}
}Equivalent Python Program:
def sum_dig(n):
s = 0
# Add each digit by repeatedly taking the last digit.
while n > 0:
s = s + n % 10
n = n // 10
return s
def sum_prime_fact(n):
i = 2
total = 0
# Divide by factors one by one and add their digit sums.
while n > 1:
if n % i == 0:
total = total + sum_dig(i)
n = n // i
else:
i = i + 1
return total
n = int(input("Enter a Number: "))
# Compare the digit sum of the number with the digit sum of its prime factors.
a = sum_dig(n)
b = sum_prime_fact(n)
print("Sum of Digit =", a)
print("Sum of Prime Factor =", b)
if a == b:
print("It is a Smith Number")
else:
print("It is Not a Smith Number")Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.