ABA12D - Sum of divisors!

no tags 

Note: 
If you really want to learn something by solving this problem, don't hard code! 
There is a nice logic behind this!

---

Kartheeswaran was recently reading an article on perfect numbers, whose sum of divisors equals twice the number. He was intrigued by them and decided to generate them but to his disappointment they turned out to be quite rare. So he decided to look out for a different property related to sum of divisors. What is more interesting than a number being a prime? So he decided to look out for numbers whose sum of divisors is a prime number and he was the inventor of these special numbers he gave them the name K-numbers.
Given a range [A,B] you are expected to find the number of K-numbers in this range.

Input

The first line of input indicates the number of test cases T.
Then in the following T lines there will be a pair of integers A and B.

Output

Output T lines each containing a single integer ‘c’ which denotes the number of K-numbers which lie in the interval [A,B] inclusive of the end points.
Constraints:
1<=T<=10000
1<=A<=B<=10^6

Example

Input:
2
1 5
9 10
Output:
2
1
Explanation of sample case:
1) In the range [1,5] the K-numbers are 2 and 4 because
Divisors of 2 are 1 and 2 which sum up to 3, which is a prime.
Divisors of 4 are 1,2 and 4 which sum up to 7, which is a prime.
 
2) The K-number in the range [9,10] is 9.

hide comments
kspoj: 2017-11-30 09:21:22

hardcoded :(

sahil070197: 2017-11-24 09:21:34

It's really nice :)
Spoiler alert
https://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number

Last edit: 2017-11-24 09:24:02
sonudoo: 2017-06-15 16:24:43

I factorized only the numbers which are perfect squares. There has to be a better way to solve this..

tusharuppal: 2017-06-14 11:43:50

easy one...AC in one go ;-)

adm2215: 2017-04-10 19:55:17

Implemented brute force approach but got TLE , eventually hard coded . ;((

amulyagaur: 2017-03-16 10:24:54

https://oeis.org/A023194

cake_is_a_lie: 2017-03-06 02:49:13

Rather than say "If you really want to learn something by solving this problem, don't hard code!", you might as well have increased the time limit to ~3s and the query limit to 10^12; that would have made hard-coding without the proper solution impractical.

coder_hsnake: 2017-02-01 15:08:57

can take help from
https://oeis.org/search?q=sum+of+divisors+prime&sort=&language=&go=Search
but do not make an array of answers try to implement the logic

piyushmittal: 2017-02-01 09:10:39

very good question...
I take much more time to solve this problem.

madhavgaba: 2017-01-19 11:06:29

perhaps the logic is that there exist only 37 such integers in 1 and 10^6............only hard code gave AC:(

Last edit: 2017-01-19 11:07:01

Added by:Kashyap Krishnakumar
Date:2012-01-13
Time limit:0.103s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem