SmoothDivisors | Topcoder Archive

Problem Statement

This problem has a time limit of 4 seconds. The memory limit is standard: 256 MB.

A set of integers is called smooth if it can be arranged into a cyclic sequence such that no pair of adjacent elements is coprime. (See Notes for a definition of "coprime".)

(An empty sequence has no pairs of adjacent elements. In a one-element sequence the only element is considered to be its own neighbor and therefore there is one pair of adjacent elements.)

Examples:

The set {1, 2, 3, 4, 5} is not smooth because in any cyclic sequence the number 1 has to have two neighbors and it will be coprime with each of them, regardless of what they are.
The set {2, 4, 6, 8, 10} is smooth: in fact, any cyclic sequence of these elements works as each two of them have a common factor that is at least 2.
The set {2, 4, 27, 54, 666} is smooth: e.g., the cyclic sequence 4, 2, 666, 27, 54 has the desired property.
The set {2, 5, 10000} is not smooth. In particular, the sequence 2, 10000, 5 does not work - remember that the sequence is cyclic and therefore 2 and 5 must also have a common factor that is greater than 1.
The empty set is smooth, with the empty sequence as a witness.
The set {1} is not smooth.
The set {42} is smooth.

Proper divisors of a positive integer X are positive integers that divide X and lie strictly between 1 and X itself. For example, 1 and 47 each have no proper divisors, and 14 has two proper divisors: 2 and 7.

A number is called smooth if the set of its proper divisors is smooth.

You are given two integers A and B. Count all smooth integers in the closed range [A, B].

Definition

Class:: SmoothDivisors
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int A, int B)
(be sure your method is public)

Notes

Positive integers X and Y are called coprime if their greatest common divisor is 1.

Constraints

1 <= A <= B <= 40,000,000.

Examples

```
213
```
```
219
```
```
Returns: 1
```
The only smooth number in this range is 216.
```
47
```
```
49
```
```
Returns: 3
```
All three numbers in this range are smooth. The set of proper divisors of 47 is {}, the set of proper divisors of 48 is { 2, 3, 4, 6, 8, 12, 16, 24 }, and the set of proper divisors of 49 is { 7 }.
```
1
```
```
5
```
```
Returns: 5
```
Again, all five numbers in this range are smooth.
```
34000046
```
```
34000046
```
```
Returns: 0
```
This number is not smooth.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.