DCP-513: Charming Numbers Back to All Problems

Medium Math > Number Theory


You task is to find the count of charming numbers on the given interval. The number is called charming if it is made of three various odd prime numbers. More formally the number **N** is charming if it can be represented as **P * Q * R** and **P**, **Q**, **R** are distinct odd prime numbers. Input: ------ The first line of input contains a number **T** of test cases (**1 ≤ T ≤ 100000**). Each following line represents one test case and consists of two positive numbers **L** and **R** denoting the left and right ends of the interval (**1 ≤ L ≤ R ≤ 200000000**). Output: ------- For each test case display the case number (they are numbered sequentially starting from 1) and the resulting number of charming numbers on the given interval (inclusive). Sample Input ------------ 3 1 100 1 200 199998160 199998170 Sample Output ------------- Case 1: 0 Case 2: 3 Case 3: 3 Memory Limit is very tight for this problem - 256MB. Seems like some verdict for MLE are giving RTE. Please try for memory optimized solution.


Problem Setter:

Feodor Volonter

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 4.00
Go 4.00
Java 4.00
JavaScript 4.00
Objective-C 4.00
Perl 4.00
PHP 4.00
Python 4.00
Python3 4.00
Ruby 4.00
VB.Net 4.00

Problem Stats

16/193

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 1.47s
02 rayhan50001 Cpp14 1.50s
03 rajdipsaha Cpp 1.81s
04 tariqiitju Cpp14 2.00s
05 cjoa Cpp 2.51s
06 Tourist Cpp14 3.05s
07 Informatimukas Cpp 3.57s
08 radoslav11 Cpp14 3.87s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support