UVa 10699

From Algorithmist
Jump to: navigation, search

10699 - Count the factors[edit]

Summary[edit]

Compute the number of different prime factors in a positive integer. (There's no markup, that's pretty much the problem.)

Explanation[edit]

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.

Input[edit]

289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0

Output[edit]

289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3