rasta-and-tavas

Rasta calls a number like a Tavas if and only if 1 ≤ a ≤ n and the sum of all primes (like p) that p | a is exactly equal to k.

He asks you to find the number of Tavases.

Input format
The first and only line of input contains two integers, n and k (1 ≤ n, k ≤ 10^6).

Output format
Print a single integer, the number of Tavases.

SAMPLE INPUT
20 7

SAMPLE OUTPUT
3

Explanation

The only Tavases are 7, 10 and 20.

Source: hackerearth | Difficulty: EASY
Tags: Complete search


Solutions:
maxn = 1000010
p = [0] * maxn
d = [0] * maxn

for i in range(2, maxn):
	if p[i] == 0:
		for j in range(i, maxn, i):
			d[j] += i
		for j in range(2 * i, maxn, i):
			p[j] = 1
		   
n, k = list(map(int, input().split()))

res = 0
for i in range(1, n+1):
	if d[i] == k:
		res+=1
print(res)        
			
		   
		   


n,k=list(map(int,input().split()))
s=[0]*(n+1)
for i in range(2,n+1):
	if(s[i]==0):
		j=i;
		while j<=n:
			s[j]=s[j]+i
			j=j+i
count=0
for i in range(n+1):
	if(s[i]==k):
		count+=1;
print(count)


n, k = list(map(int, input().split()))

li = [0] * (n+2)

i = 2
while i<=n:
	if li[i]==0:
		j = i
		while j<=n:
			li[j] += i
			j += i
	i += 1

print(li.count(k))
	



def seive():
	p = [0] * 1000001
	for i in range(2, 1000001):
		if not p[i]:
			j = i
			while j < 1000001:
				p[j] += i
				j += i
		   
	return p

prim = seive()
n, k = list(map(int, input().split()))
cnt = 0
for i in range(1, n+1):
	if prim[i] == k:
		cnt += 1
print(cnt)        
	
				


n,k=list(map(int,input().split()))
s=[0]*(n+1)
for i in range(2,n+1):
	if(s[i]==0):
		for j in range(i,n+1,i):
			s[j]=s[j]+i
count=0
for i in range(n+1):
	if(s[i]==k):
		count+=1;
print(count)