what will be a c programme to get number of zeroes at the end of 1000! = 2*3*4*.....1000?

Answer 1

The idea: The number of zeroes at the end of 1000! will be the number of times we can divide it by 10 with no remainder. If we find out the number of 2's and 5's in the prime factorization of 1000!, then the number of zeroes at the end will be whichever of these is less.

Note that a couple of lines in the program below might have wrapped, so you might have to edit it slightly if you actually want to compile this program.

The answer will be 249, as the person above me has discovered analytically.

---

#include

int twos_in(int n);
int fives_in(int n);

int main(void) {
int i;
int twos = 0;
int fives = 0;

for(i = 1; i <= 1000; ++i) {
twos += twos_in(i); /* Count the number of twos in the prime factorization of i */
fives += fives_in(i); /* Count the number of fives in the prime factorization of i */
}

/* We'll be able to divide 1000! by 10 until we run out of 2's or 5's */
if (twos < fives) {
printf("%d zeroes\n", twos);
} else {
printf("%d zeroes\n", fives);
}

return 0;
}

int twos_in(int n) {
int twos = 0;

/* Divide n by 2 until we can't any more */
while (n % 2 == 0) {
n /= 2;
++twos;
}
return twos;
}

int fives_in(int n) {
int fives = 0;

/* Divide n by 5 until we can't any more */
while (n % 5 == 0) {
n /= 5;
++fives;
}
return fives;
}

Answer 2

Factor it. The number of 2s and 5s in the factored number that can be paired off will be the number of zeros at the end. Clearly there will be more 2s. So the number of 5s is limiting.

The number of 5s is:

Every fifth number has a five.
Every 25th number has two fives (5²).
Every 125th number has three fives (5³)
Every 625th number has four fives (5^4)

Total number of fives is:

1000/5 + 1000/25 + 1000/125 + 1

= 200 + 40 + 8 + 1 = 249

There will be 249 zeros at the end of 1000!