BinString

PROBLEM STATEMENT

Class: BinString
Method: getNumPrim
Arguments: int
Returns: int

Implement a class BinString containing a method getNumPrim, which returns the
total number of primitive strings that can be found among all binary strings of
length n. A binary string is a string composed of only zeros and ones. A
primitive string is defined as a string of zeros and ones such that it cannot
decomposed of a single smaller substring repeated an integer number of times.
For example, "1011" is a primitive string. "1010" is not a primitive string,
since it can be comprised of "10", twice in a row. "10101" is a primitive
string, since no smaller substring of "10101" can be repeated an integer number
of times to form "10101". "100100100" is not a primitive string; "100" can be
repeated 3 times to form "100100100"

So, given a length n, determine how many of all possible binary strings of
length n are primitive.

Here is the method signature(make sure your method is public): int
getNumPrim(int n);

TopCoder will verify that n is between 1 and 25, inclusive.

EXAMPLES

n = 4

"0000" is not primitive
"0001" is primitive
"0010" is primitive
"0011" is primitive
"0100" is primitive
"0101" is not primitive
"0110" is primitive
"0111" is primitive
"1000" is primitive
"1001" is primitive
"1010" is not primitive
"1011" is primitive
"1100" is primitive
"1101" is primitive
"1110" is primitive
"1111" is not primitive
So the method returns 12.

more examples:
n = 3 -> returns 6
n = 6 -> returns 54
n = 11 -> returns 2046
n = 9 -> returns 504