Identify Smith Numbers

A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding ). The first few such numbers are 4,22,27,58,85,94, and 121.

Explanation

N = 378

Its prime factors are 2,3,3,3,7.
The sum of its digits is (3+7+8) = 18.
The sum of the digits of its factors is (2+3+3+3+7) = 18.

Example:

Input:  n = 378
Output: 1

Approach

Java

import java.util.ArrayList;

public class SmithNumber {
    public static void main(String[] args) {

        int n = 378;
        System.out.println(solve(n));

    }

    static ArrayList<Integer> prime = new ArrayList<Integer>();

    static int maxn = (int) (1e6 + 1);
    static int primeArr[];

    static void seive() {

        primeArr = new int[maxn + 10];
        for (int i = 2; i * i < maxn; i++) {
            if (primeArr[i] == 0)
                for (int j = i * i; j < maxn; j += i)
                    primeArr[j] = 1;
        }
        for (int i = 2; i <= maxn; i++)
            if (primeArr[i] == 0)
                prime.add(i);
    }

    static int solve(int n) {

        seive();
        int x = n;
        ArrayList<Integer> factors = new ArrayList<Integer>();
        for (int i = 0; prime.get(i) <= x; i++) {
            while (x % prime.get(i) == 0) {
                x /= prime.get(i);
                factors.add(prime.get(i));
            }
        }
        int sum1 = 0;
        x = n;

        // find sum of digits of a number
        while (x > 0) {
            sum1 += x % 10;
            x /= 10;
        }
        int sum2 = 0;

        // find sum of digits of all
        // the factors of the given
        // number
        for (int i : factors) {
            x = i;
            while (x > 0) {
                sum2 += x % 10;
                x /= 10;
            }
        }

        // if both sums are same then
        // return 1
        if (sum1 == sum2)
            return 1;

        // otherwise return 0
        return 0;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> prime;
const int maxn = 1e6 + 1;
bool primeArr[maxn];

void seive()
{
    memset(primeArr, 1, sizeof(primeArr));
    for (int i = 2; i * i < maxn; i++)
    {
        if (primeArr[i])
            for (int j = i * i; j < maxn; j += i)
                primeArr[j] = 0;
    }
    for (int i = 2; i <= maxn; i++)
        if (primeArr[i])
            prime.push_back(i);
}
int solve(int n)
{

    seive();
    int x = n;
    vector<int> factors;
    for (int i = 0; prime[i] <= x; i++)
    {
        while (x % prime[i] == 0)
        {
            x /= prime[i];
            factors.push_back(prime[i]);
        }
    }
    int sum1 = 0;
    x = n;

    //find sum of digits of a number
    while (x)
    {
        sum1 += x % 10;
        x /= 10;
    }
    int sum2 = 0;

    //find sum of digits of all
    //the factors of the given
    //number
    for (auto i : factors)
    {
        x = i;
        while (x)
        {
            sum2 += x % 10;
            x /= 10;
        }
    }

    //if both sums are same then
    //return 1
    if (sum1 == sum2)
        return 1;

    //otherwise return 0
    return 0;
}

int main()
{

    int n = 378;
    cout << solve(n) << "\n";

    return 0;
}