Refactoring
SRM 216 · 2004-10-18 · by dgarthur
SRM 216 · 2004-10-18 · by dgarthur · Brute Force, Simple Math
Problem Statement
Problem Statement
You have been hired to do some refactoring. You are not really sure what that is, but you think it has something to do with factoring a number multiple times.
Recall that a factorization of a positive integer n is a collection of at least two positive integers, each larger than one, whose product is n. Note that the order of the numbers in a factorization is ignored, so 2*12 and 12*2 represent the same factorization of 24. In fact, 24 has precisely 6 valid factorizations: 2*2*2*3, 2*2*6, 2*3*4, 2*12, 3*8, and 4*6.
To prepare for your job, write a program that, given anint n, returns the number of unique factorizations of n.
Recall that a factorization of a positive integer n is a collection of at least two positive integers, each larger than one, whose product is n. Note that the order of the numbers in a factorization is ignored, so 2*12 and 12*2 represent the same factorization of 24. In fact, 24 has precisely 6 valid factorizations: 2*2*2*3, 2*2*6, 2*3*4, 2*12, 3*8, and 4*6.
To prepare for your job, write a program that, given an
Constraints
- n will be between 2 and 2,000,000,000 inclusive.
Examples
0)
24 Returns: 6
This is the example from the problem statement.
1)
9973 Returns: 0
9973 is a prime number, so there are no valid factorizations of 9973.
2)
9240 Returns: 295
3)
1916006400 Returns: 7389115
The number of factorizations will never be larger than this.
4)
2000000000 Returns: 36534
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Refactoring with a public method int refactor(int n) · 67 test cases · 2 s / 256 MB per case