0031. Primesets

Input file name: primeset.in
Output file name: primeset.out
Time limit: 20 s
Memory limit: 64 megabytes

Your task is to count all groups of three natural numbers a1, a2, a3 in range A≤ ai≤ B which have the property that any selected two of them are relatively prime. For example, when A=1 and B=2 there are only four groups: (1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1).

Input file

The input file consists of two integer numbers A and B, where 1≤ A≤ B ≤ 30000 and B-A≤ 1700.

Output file

You are to output the number of such groups.


1 2 4

Source: Petrozavodsk training camp, Summer 2002. Startup contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution

Printable version