Smith Number - GeeksforGeeks

Smith Number - GeeksforGeeks
Given a number n, the task is to find out whether this number is smith or not. A Smith Number is a composite number whose sum of digits is equal to the sum of digits in its prime factorization.

const int MAX  = 10000;

 

// array to store all prime less than and equal to 10^6

vector <int> primes;

 

// utility function for sieve of sundaram

void sieveSundaram()

{

    // In general Sieve of Sundaram, produces primes smaller

    // than (2*x + 2) for a number given number x. Since

    // we want primes smaller than MAX, we reduce MAX to half

    // This array is used to separate numbers of the form

    // i+j+2ij from others where 1 <= i <= j

    bool marked[MAX/2 + 100] = {0};

 

    // Main logic of Sundaram. Mark all numbers which

    // do not generate prime number by doing 2*i+1

    for (int i=1; i<=(sqrt(MAX)-1)/2; i++)

        for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)

            marked[j] = true;

 

    // Since 2 is a prime number

    primes.push_back(2);

 

    // Print other primes. Remaining primes are of the

    // form 2*i + 1 such that marked[i] is false.

    for (int i=1; i<=MAX/2; i++)

        if (marked[i] == false)

            primes.push_back(2*i + 1);

}

 

// Returns true if n is a Smith number, else false.

bool isSmith(int n)

{

    int original_no = n;

 

    // Find sum the digits of prime factors of n

    int pDigitSum = 0;

    for (int i = 0; primes[i] <= n/2; i++)

    {

        while (n % primes[i] == 0)

        {

            // If primes[i] is a prime factor,

            // add its digits to pDigitSum.

            int p = primes[i];

            n = n/p;

            while (p > 0)

            {

                pDigitSum += (p % 10);

                p = p/10;

            }

        }

    }

 

    // If n!=1 then one prime factor still to be

    // summed up;

    if (n != 1 && n != original_no)

    {

        while (n > 0)

        {

            pDigitSum = pDigitSum + n%10;

            n = n/10;

        }

    }

 

    // All prime factors digits summed up

    // Now sum the original number digits

    int sumDigits = 0;

    while (original_no > 0)

    {

        sumDigits = sumDigits + original_no % 10;

        original_no = original_no/10;

    }

 

    // If sum of digits in prime factors and sum

    // of digits in original number are same, then

    // return true. Else return false.

    return (pDigitSum == sumDigits);

}

Read full article from Smith Number - GeeksforGeeks