You need to add two temporary variables.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n1, n2, sum, tmp, digit;
printf("Enter the lower limit: ");
scanf("%d", &n1);
printf("\nEnter the upper limit: ");
scanf("%d", &n2);
while (n1 <= n2) {
sum = 0;
tmp = n1;
while (tmp != 0) {
digit = tmp % 10;
sum += digit * digit * digit;
tmp = tmp / 10;
}
if (sum == n1) {
printf("%d\n", n1);
}
n1++;
}
exit(EXIT_SUCCESS);
}
Problem: does not calculate all Armstrong numbers (obligatory OEIS link) only the three digit ones. To compute all n-narcissistic numbers you need to know the number of decimal digits and compute the power accordingly. As a short sketch:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// ALL CHECKS OMMITTED!
int decimal_digits(int number)
{
// actually wrong, but we don't use negative numbers here
// and can safely set log(0) = 1
if (number <= 0) {
return 1;
}
return (int) (floor(log10(number)) + 1);
}
int main()
{
int n1, n2, sum, tmp, digit, dec_digits;
printf("Enter the lower limit: ");
scanf("%d", &n1);
printf("\nEnter the upper limit: ");
scanf("%d", &n2);
while (n1 <= n2) {
sum = 0;
dec_digits = decimal_digits(n1);
tmp = n1;
while (tmp != 0) {
digit = tmp % 10;
sum += (int) (floor(pow((double) digit, (double) dec_digits)));
tmp = tmp / 10;
}
if (sum == n1) {
printf("%d\n", n1);
}
n1++;
}
exit(EXIT_SUCCESS);
}
But that is really only a sketch! A lot of ugly casting and even more assumptions about the environment etc.!
Finds the Armstrong numbers up to 1741725 quite quickly but needs a couple of minutes for the rest (still at 146511208 after 5 minutes). There is a lot of room for optimization.
EDIT found some time (obligatory XKCD) for two experiments.
The code above needs about 10.5 minutes to find the first 34 Armstrong numbers (low limit = 0, high limit = 912985154). If we get rid of the functions from the math-library and roll our own we can save more than half of that run-time.
#include <stdio.h>
#include <stdlib.h>
// ALL CHECKS OMMITTED!
int decimal_digits(int number);
/*
* If you know for sure that e.g.: sizeof(unsigned long)*CHAR_BITS = 32
* and sizeof(unsigned long long)*CHAR_BITS = 64 you can replace
* the inclusion of stdint.h with the following type definitions
*
* For 32 bit x86:
* typedef unsigned int uint32_t;
* typedef unsigned long long int uint64_t;
*
* For 64 bit x86:
* typedef unsigned int uint32_t;
* typedef unsigned long int uint64_t;
*/
#include <stdint.h>
uint64_t own_pow(uint32_t base, uint32_t exponent);
uint32_t own_ilogb(uint32_t base, uint32_t n);
int decimal_digits(int number)
{
// actually wrong, but we don't use negative numbers here
// and can safely set log(0) = 1
if (number < 10) {
return 1;
}
return (int) (own_ilogb(10,(uint32_t) number) + 1);
}
uint64_t uipow(uint32_t base, uint32_t exponent)
{
uint64_t power = 1;
uint64_t big_base = (uint64_t) base;
while (exponent) {
if (exponent % 2 == 1) {
power *= big_base;
}
exponent >>= 1;
big_base *= big_base;
}
return power;
}
uint32_t own_ilogb(uint32_t base, uint32_t n)
{
uint32_t low = 0, big_low = 1, high = 1, mid, big_mid;
uint64_t big_high = base;
// interval reduction (more useful for big-integers)
while (big_high < n) {
low = high;
big_low = big_high;
high <<= 1;
big_high *= big_high;
}
// the actual bisection
while ((high - low) > 1) {
mid = (low + high) >> 1;
big_mid = big_low * uipow(base, mid - low);
if (n < big_mid) {
high = mid;
big_high = big_mid;
}
if (n > big_mid) {
low = mid;
big_low = big_mid;
}
if (n == big_mid)
return mid;
}
if (big_high == n) {
return high;
}
return low;
}
int main()
{
int n1, n2, sum, tmp, digit, dec_digits;
printf("Enter the lower limit: ");
scanf("%d", &n1);
printf("\nEnter the upper limit: ");
scanf("%d", &n2);
while (n1 <= n2) {
sum = 0;
dec_digits = decimal_digits(n1);
tmp = n1;
while (tmp != 0) {
digit = tmp % 10;
sum += (int) uipow((uint32_t) digit, (uint32_t) dec_digits);
tmp = tmp / 10;
}
if (sum == n1) {
printf("%d\n", n1);
}
n1++;
}
exit(EXIT_SUCCESS);
}
(run in 4 minutes and 7 seconds for the range listed above)
The binary search algorithm for own_ilogb() looks slow, we could exchange that with
// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
// vid.: http://stackoverflow.com/questions/7365562/de-bruijn-like-sequence-for-2n-1-how-is-it-constructed for an explanation
static const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31
};
static int ilog2(uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t) (value * 0x07C4ACDD) >> 27];
}
int decimal_digits(int number)
{
double logten2two = 3.3219280948873623478703194294893901759;
// actually wrong, but we don't use negative numbers here
// and can safely set log(0) = 1
if (number < 10) {
return 1;
}
return (int) (ilog2((uint32_t) number) / logten2two + 1.0);
}
This does not save a lot of time--it runs in 3 minutes 38 seconds--but half a minute is not nothing.
Using compiler (GCC 4.8.1) optimization -O3 : 3 minutes 43 seconds
A bit slower (about the same, I just used time and it was not the only process running here)
The outer loop invites to try a parallel approach (here with OpenMP to keep things simple)
int main()
{
int n1, n2, sum, tmp, digit, dec_digits;
int iter;
printf("Enter the lower limit: ");
scanf("%d", &n1);
printf("\nEnter the upper limit: ");
scanf("%d", &n2);
#pragma omp parallel for
for(iter = n1;iter <= n2;iter++) {
sum = 0;
dec_digits = decimal_digits(iter);
tmp = iter;
while (tmp != 0) {
digit = tmp % 10;
sum += (int) uipow((uint32_t) digit, (uint32_t) dec_digits);
tmp = tmp / 10;
}
if (sum == iter) {
printf("%d\n", iter);
}
}
exit(EXIT_SUCCESS);
}
That runs in 2 minutes 15 seconds (user: 8m11.933s because 4 CPUs were working at it in parallel and "user" adds all up), although the output is unsorted, of course.
PS: A lot of C&P involved in this post which might have caused one or the other error here and there. Please inform me about the, in the comments below such that I can repair them.
