UVa 10699
From Algorithmist
Contents |
[edit] 10699 - Count the factors
[edit] Summary
Compute the number of different prime factors in a positive integer. (There's no markup, that's pretty much the problem.)
[edit] Explanation
Use a modified Prime Sieve of Eratosthenes: Instead of holding a boolean array, use an integer array, and increment as you sieve through each prime.
[edit] Input
289384 930887 692778 636916 747794 238336 885387 760493 516650 641422 0
[edit] Output
289384 : 3 930887 : 2 692778 : 5 636916 : 4 747794 : 3 238336 : 3 885387 : 2 760493 : 2 516650 : 3 641422 : 3
