SquareFreeNumbers
TCO09 Qual 1 · 2009-02-24 · by FedorTsarev
TCO09 Qual 1 · 2009-02-24 · by FedorTsarev · Math
Problem Statement
Problem Statement
A number is called square-free if it is not divisible by a perfect square which is greater than one. A perfect square is the square of an integer. Return the number of square-free numbers between min and max, inclusive.
Constraints
- min will be between 1 and 1,000,000,000,000, inclusive.
- max will be between min and (min + 1,000,000), inclusive.
Examples
0)
1 10 Returns: 7
Numbers 4, 8 and 9 are not square-free.
1)
15 15 Returns: 1
min and max can be equal.
2)
1 1000 Returns: 608
3)
1 1000001 Returns: 607927
4)
123456 234567 Returns: 67553
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SquareFreeNumbers with a public method int getCount(long long min, long long max) · 139 test cases · 2 s / 256 MB per case