Smith numbers | Rosetta Code | #23
URL to the problem page: https://rosettacode.org/wiki/Smith_numbers
Smith numbers are numbers such that the sum of the decimal digits of the integers that make up that number is the same as the sum of the decimal digits of its prime factors excluding 1.
By definition, all primes are excluded as they (naturally) satisfy this condition!
Smith numbers are also known as joke numbers.
Example
Using the number 166
Find the prime factors of 166 which are: 2 x 83
Then, take those two prime factors and sum all their decimal digits: 2 + 8 + 3 which is 13
Then, take the decimal digits of 166 and add their decimal digits: 1 + 6 + 6 which is 13
Therefore, the number 166 is a Smith number.
Write a program to find all Smith numbers below 10000.
#include <iostream>
using namespace std;
int n = 0, factors[512] = { 0 }, multiply = 1, thenumber = 0;
int power(int a, int b);
bool primecheck(int a);
void factorization(int a);
void factorization(int a) {
int cnt = 0;
for (int i = 2; i <= (a / 2); i++) {
if (a % i == 0) {
if (cnt == 0 && primecheck(i) == 0) {
continue;
}
cnt++;
if (primecheck(i) == 0) {
factorization(i);
}
else {
factors[n] = i;
n++;
multiply *= i;
}
if (primecheck(a / i) == 0) {
factorization(a / i);
}
else {
factors[n] = a / i;
n++;
multiply *= (a / i);
}
}
if (multiply == thenumber) {
break;
}
}
}
bool primecheck(int a) {
int cnt = 0;
for (int i = 2; i <= sqrt(a); i++) {
if (a % i == 0) {
cnt++;
break;
}
}
if (cnt == 0) {
return 1;
}
else {
return 0;
}
}
int power(int a, int b) {
int result = 1;
for (int i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main()
{
cout << "Smith numbers below 10.000 are:" << endl << endl;
int sum, sum2, tmp, digitnumber, qnt = 0;
for (int i = 1; i < 10000; i++) {
if (primecheck(i) == 1) {
continue;
}
sum = 0;
sum2 = 0;
tmp = i;
digitnumber = 1;
while (tmp >= 10) {
tmp /= 10;
digitnumber++;
}
for (int k = 1; k <= digitnumber; k++) {
sum += ((i % power(10, k)) / power(10, (k - 1)));
}
for (int k = 0; k < 512; k++) {
factors[k] = 0;
}
n = 0;
multiply = 1;
thenumber = i;
factorization(i);
for (int j = 0; factors[j] > 0; j++) {
tmp = factors[j];
digitnumber = 1;
while (tmp >= 10) {
tmp /= 10;
digitnumber++;
}
for (int k = 1; k <= digitnumber; k++) {
sum2 += ((factors[j] % power(10, k)) / power(10, (k - 1)));
}
}
if (sum == sum2) {
cout << i << ", ";
qnt++;
if (qnt % 25 == 0) {
cout << endl;
}
}
}
cout << endl << endl << qnt << " smith numbers in total." << endl;
}
Comments
Post a Comment