PROBLEM STATEMENT
Every positive integer greater than one is prime or can be uniquely represented
as a product of prime numbers. For example:
60 = 2*2*3*5
A positive number that is only divisible by itself and 1 is a prime number.
The lowest prime number is 2.
The problem is, we are beginning to run out of prime numbers and are now
keeping a close eye on anyone who is using them up. In the previous example,
the number 60 used up two 2s, one 3, and one 5, so in total, it used up four
primes. Given a list of numbers, return how many prime numbers they use up. A
prime number uses up one prime, whereas a non-prime number uses up however many
primes it is a product of. See examples for more clarification.
Create a class PrimeCount that contains the method howMany, which takes an
int[] numbers, and returns an int that represents how many prime numbers were
used.
DEFINITION
Class: PrimeCount
Method: howMany
Parameters: int[]
Returns: int
Method signature (be sure your method is public): int howMany(int[] numbers);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- numbers will contain between 1 and 50 elements inclusive
- Each element of numbers will be between 2 and 1000000000 (10^9) inclusive
EXAMPLES
1) numbers = {4,4,5,60,100}
4 = 2*2
4 = 2*2
5 = 5
60 = 2*2*3*5
100 = 2*2*5*5
So 4 used up two primes each time it was used, 5 used up one prime, 60 used up
four primes and 100 used up four primes. 2+2+1+4+4 = 13.
Method returns 13.
2) numbers = {15,9,81,144}
15 = 3*5
9 = 3*3
81 = 3*3*3*3
144 = 2*2*2*2*3*3
So 15 used up two primes, 9 used up two, 81 used up four, and 144 used up six.
2+2+4+6 = 14.
Method returns 14.
3) numbers = {23,17,19,2}
23 = 23
17 = 17
19 = 19
2 = 2
1+1+1+1 = 4.
Method returns 4.
4) numbers = {999999,999998,999997,4098,177777}
Method returns 19.
5) numbers = {2,2,2,2,100,100,100,100,2,3,4,5,6,7,8,9,10}
Method returns 35.
6) numbers = {1000000000,1000000000,999999999,999999999,999999999}
Method returns 54.
7) numbers = {736217429,729905947,630403687,918545629,960778619,894348149}
Method returns 6.
8) numbers = {2,2}
Method returns 2.
9) numbers = {3}
Method returns 1.