Algorithm
Problem link- https://www.spoj.com/problems/ABA12D/
ABA12D - Sum of divisors!
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
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 only K-number in the range [9, 10] is 9
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
a = [2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041,
7921, 10201, 15625, 17161, 27889, 28561, 29929, 65536, 83521,
85849, 146689, 262144, 279841, 458329, 491401, 531441, 552049,
579121, 597529, 683929, 703921, 707281, 734449, 829921]
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
result = 0
for i in a:
if N <= i <= M:
result += 1
print(resultInput
1 5
9 10
Output
1
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MOD 1000000007
#define MAX 100000
typedef unsigned long long ull;
int N,M;
#define MAX 1000000
bool isNPrime[10000000];
int Primes[3000000], nPrimes=0;
int knum[100], kn=0;
int seive()
{
isNPrime[0]=isNPrime[1]=true;
for(int i=0;i*i<4*MAX;i++)
if(isNPrime[i]==false)
for(int j=i*i;j<4*MAX;j=j+i)
isNPrime[j]=true;
for(int i=0;i<4*MAX;i++)
if(isNPrime[i]==false)
Primes[nPrimes++]=i;
}
int pow1(int x, int n){
if(n==0) return 1;
int r = pow1(x, n/2);
r=r*r;
if(n%2==1)
r=r*x;
return r;
}
int dev(int n){
int res=1;
if(isNPrime[n]==false)
return n+1;
for(int i=0;i<nPrimes && Primes[i]<=n;i++){
int cnt=0;
while(n%Primes[i]==0) {
n=n/Primes[i]; cnt++;
}
if(cnt){
res = res * (pow1(Primes[i], cnt+1) - 1) / (Primes[i]-1);
}
}
return res;
}
int main(){
seive();
// cout << dev(50) << endl;
knum[kn++]=2;
for(int i=1;i*i<=MAX;i++){
int k = dev(i*i);
if(isNPrime[k]==false)
knum[kn++] = i*i;
}
int T, a, b;
cin >> T;
while(T--)
{
cin >> a >> b;
int ai,bi;
for(ai=0;ai<kn && knum[ai]<a;ai++);
for(bi=kn-1;bi>=0 && knum[bi]>b;bi--);
// cout << ai << ' ' << bi << endl;
cout << bi-ai+1 << endl;
}
return 0;
}Input
1 5
9 10
Output
1
Demonstration
SPOJ Solution-Sum of divisors!-Solution in C, C++, Java, Python