ashu-and-prime-factors-4

Ashu is very fond of Prime numbers and he like challenging his friends by giving them various problems based on Mathematics and Prime number. One of his friend Harshit is jealous and challenges him to solve a task. Task is :Given a prime number X, you need to give the count of all numbers in range 1 to 10^6 inclusive which  have minimum prime factor X.Help Ashu in solving this task.Input:First line consist of numer of test cases T.Each test case contains a single number X.Output:Output for each test case count of all numbers in range 1 to 10^6 inclusive which  have minimum prime factor X.Constraints:1 ≤ T ≤ 10^5Prime number X where 2 ≤ X ≤ 10^6

SAMPLE INPUT
2
2
11

SAMPLE OUTPUT
500000
20779

Explanation

The minimum prime factor of all even numbers in the range [2, 1000000] is 2, and there are 1000000/2 = 500000 such even numbers.
The numbers with minimum prime factor as 11 are: 11, 121, 143, ...

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
MAX = 10**6+1
primes = [1]*MAX
primes[0] = primes[1] = 0
for i in range(2,MAX):
	if primes[i]:
		for j in range(i*i,MAX,i):
			if primes[j]:
				primes[i] += 1
				primes[j] = 0
for _ in range(eval(input())):
	x = eval(input())
	print(primes[x])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

L=[]
prime=[]
for y in range(1000001):
	L.append(0)
for x in range(2, 1000001):
	if L[x]==0:
		L[x]=x
		if x<1000:
			prime.append(x)
		for z in range(x, 1000000/x+1):
			if (L[x*z])==0:
				L[x*z]=x
N=[]
L.sort()
for j in prime:
	i=L.index(j)
	f=L[::-1].index(j)
	N.append(1000001-i-f)


		
for i in range(int(input())):
	n=int(input())
	if n>1000:
		print(1)
	else:
		print(N[prime.index(n)])
	

		




	
		
	
	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


from bisect import bisect


C = 1000000
lst = [0]*(C + 1)
lst[0] = 0
lst[1] = 1

ans = {}

for i in range(2, C + 1):
	if lst[i] == 0:
		ans[i] = 1
		lst[i] = i
		j = 2*i
		while j <= C:
			if lst[j] == 0:
				ans[i] += 1
				lst[j] = i
			j += i

	
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	print(ans[n])


import math
def getAllPrime(n):
	primes = []
	num = {}
	for i in range(n):
	    primes.append(0)

	for i in range(1, n-1):

		if primes[i]==0:
			primes, count = mark_multiples(primes, i+1, n)
			num[i+1] = count+1
			#print num
		else:
			continue
	return num
	
def mark_multiples(primes, a, n):
    i = 2
    num = a*i
    count =0
    while num <=n:
        if primes[num-1]== 1:
            pass
        else:
            count +=1
            primes[num-1] = 1
        i += 1
        num = a*i

    return primes, count

def checkPrime(n):
	flag = 1
	if n==2:
	    return True
	for i in range(2, int(math.sqrt(n))):
		if n%i == 0:
			return False
	return True

#def countNumber(n, primes):
	#endNum = 1000000
	#count = 0
	#if n==2:
	    #return endNum/2
	#for i in range(n, endNum):
		#if i%n == 0:
			#flag = 0
			#for prime in primes[:primes.index(n)]:
			        #print prime
				#if i%prime == 0:
					#flag = 1
					#break
			#if flag == 0:
				#count +=1
	#return count[]

def main():
	result = []
	endNum = 1000000
	num = getAllPrime(endNum)
	#print primes
	testcases = int(input())
	for i in range(testcases):
		prime = int(input())
		#result.append(countNumber(prime, primes))
		result.append(num[prime])

	for j in range(len(result)):
		print(result[j])

if __name__ == '__main__':
	main()




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
# print 'Hello World!'
if __name__ == '__main__':
	p = [1]*1000001
	ans = [1]*1001
	for i in range(2, 1001):
		if p[i]:
			for j in range(i*i, 1000001, i):
				if p[j]:
					ans[i] += 1
				p[j] = 0
	for t in range(eval(input())):
		x = eval(input())
		if x > 1000:
			print(1)
		else:
			print(ans[x])


min_fact_cnt = [0]*1000001
primes = [True]*1000001

def sieve() :
	for i in range(2,1000001) :
		if primes[i] :
			j = 2*i
			min_fact_cnt[i]=min_fact_cnt[i]+1
			while j<1000001 :
				if primes[j] :
					min_fact_cnt[i]=min_fact_cnt[i]+1
				primes[j] = False
				j=j+i
	
	
sieve()	
t = int(input())
for i in range(t) :
	p = int(input())
	#print p
	print(min_fact_cnt[p])
	    




mx = 1000001
l = []
ans = {}
for i in range(mx):
	l.append(0)
for i in range(2,mx,1):
	ct = 0
	if l[i] == 0:
		for j in range(i*i,mx,i):
			if l[j] == 0:
				l[j] = 1
				ct+=1
	ans[i] = ct+1

tc = int(input())

for i in range(tc):
	n = int(input())
	print(ans[n])


import time


vals = {}
completed = set()            
for i in range(2, 10**6+1):
	tmp = set(j for j in range(i, 10**6+1, i) if j not in completed)
	vals[i] = len(tmp)
	completed.update(tmp)



T = eval(input())
for i in range(T):
	N = eval(input())
	if N in vals:
		print(vals[N])
	else:
		print(0)


p = [1]*(1000001)
primes = []
p[0] = 0
p[1] = 0
cnt = 0
ind = [0]*1000001
cntr = [0]*(1000001)
for i in range(2, 1000001):
	if p[i] == 1:
		c = 1
		for j in range(2*i, 1000001, i):
			if p[j] != 0:
				c += 1
			p[j] = 0			
		cntr[i] = c
		primes.append(i)
		ind[i] = cnt
		cnt+=1

t = eval(input())
while t>0:
	t-=1
	n = eval(input())
	print(str(cntr[n]))


def sieve():
	for i in range(2,mx):
		if(prime[i]!=0):
			continue;
		prime[i]=i
		for j in range(2*i,mx,i):
			if(prime[j]==0):
				prime[j]=i
prime=[0]
cnt=[0]
mx= 1000001
for x in range(1,mx):
	prime.append(0)
	cnt.append(0)

sieve()
prime[1]=1
for i in range(1,mx):
	x= prime[i]
	cnt[x]+=1
'''for i in range(0,mx):
	print ("%d->%d %d")%(i,prime[i],cnt[i])'''


for x in range(eval(input())):
	n=eval(input())
	print(cnt[n])

	


p=[1]*1000001
a=[0]*1000001
c=[0]*1000001
i=2
while i<1000001:
	if p[i]==1:
		a[i]=i
		j=2
		while j*i<1000001:
			if a[j*i]==0:
				a[j*i]=i
			p[j*i]=0
			j+=1
	i+=1
i=0
while i<1000001:
	c[a[i]]+=1
	i+=1
t=int(input())
while t!=0:
	x=int(input())
	print(c[x])
	t-=1


from math import sqrt


sieve = [False for i in range(10**6 + 2)]
count = [0 for i in range(10**6 + 2)]

for i in range(2, int(sqrt(10**6 + 2))):
	for j in range(2, 10**6 + 2):
		if i*j > 10**6:
			break

		if not sieve[i*j]:
			sieve[i*j] = True
			count[i] += 1

for t in range(int(input())):
	p = int(input())
	print((count[p] + 1))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

L=[]
prime=[]
for y in range(1000001):
	L.append(0)
for x in range(2, 1000001):
	if L[x]==0:
		if x<1000:
			prime.append(x)
		for z in range(1, 1000000/x+1):
			if (L[x*z])==0:
				L[x*z]=x
N=[]
L.sort()
for j in prime:
	i=L.index(j)
	f=L[::-1].index(j)
	N.append(1000001-i-f)


		
for i in range(int(input())):
	n=int(input())
	if n>1000:
		print(1)
	else:
		print(N[prime.index(n)])
	

		




	
		
	
	
	


tc=int(input())
ans=[0]*1000001
look=[0]*1000001
for i in range(2,1000001):
	if look[i]==0:
		count=0
		for j in range(2*i,1000001,i):
			if look[j]==0:
				count+=1
				look[j]=1
		ans[i]=count
for t in range(tc):
	x=int(input())
	print(ans[x]+1)


import sys

mask = []
count = []

for i in range(1000001):
	mask.append(0)

for i in range (1001):
	count.append(1)

for i in range (2,1001):
	if(mask[i]==0):
		for j in range (i,1000000/i + 1):
			prod = i * j
			if(prod <= 1000000 and mask[prod]==0):
				mask[prod]=1
				count[i] = count[i] + 1
		
T = int(input())
for tests in range (1,T+1):
	prime = int(input())
	if(prime <= 1000):
		print(count[prime])
	else:
		print("1")



from sys import stdin

def main():
	sieve = [0]*1000001
	cache = [0]*1000001
	for x in range(2, 1000001):
		if not sieve[x]:
			for y in range(x, 1000001, x):
				if not sieve[y]:
					sieve[y] = 1
					cache[x] += 1
	nextint = iter(map(int, stdin.read().split())).__next__
	print('\n'.join([str(cache[nextint()]) for _ in range(nextint())]))

main()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


from bisect import bisect


C = 1000000
lst = [0]*(C + 1)
lst[0] = 0
lst[1] = 1

ans = [0]*(C + 1)

for i in range(2, C + 1):
	if lst[i] == 0:
		ans[i] = 1
		lst[i] = i
		j = i*i
		while j <= C:
			if lst[j] == 0:
				ans[i] += 1
				lst[j] = i
			j += i

	
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	print(ans[n])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


from bisect import bisect


C = 1000000
lst = [0]*(C + 1)
lst[0] = 0
lst[1] = 1

ans = {}

for i in range(2, C + 1):
	if lst[i] == 0:
		ans[i] = 1
		lst[i] = i
		j = i*i
		while j <= C:
			if lst[j] == 0:
				ans[i] += 1
				lst[j] = i
			j += i

	
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	print(ans[n])


#prime={}
minprime={}
freq={}
#print "hello"
#print "hello"
for i in range(1000001):
	freq[i]=0
def prime():
	for i in range(1000001):
		minprime[i]=0
	for i in range(2,1000001,2):
		minprime[i]=2
		freq[2]+=1
	for i in range(3,1000001,2):
		if minprime[i]==0:
			minprime[i]=i
			freq[i]+=1
			j=i*i
			while j<=1000000:
				if minprime[j]==0:
					minprime[j]=i
					freq[i]+=1
				j+=i
			'''for j in range(i*i,1000000,j+i):
				if j>1000000:
					break;
				else:
					if minprime[j]==0:
						minprime[j]=i'''
#print "prime enter"
prime()
#print "prime done"
t=int(input())
#print "enter tet case"
for i in range(t):
	n=int(input())
	c=0
	'''for j in range(2,1000002,1):
		if minprime[j]==n:
			c+=1'''
	print(freq[n])


arr=[0]*1000003
cnt=[0]*1000003
def sieve():
	global arr,cnt
	for i in range(2,1002):
		if arr[i]==0:
			j=2
			arr[i]=i
			cnt[i]+=1
			while ((i*j)<1000001):
				if (arr[i*j]==0):
					arr[i*j]=i
					cnt[i]+=1
				j+=1
		
sieve()
for i in range(1001,1000001):
	if arr[i]==0:
		cnt[i]+=1
		
for i in range (eval(input())):
	n=eval(input())
	print(cnt[n])
			


fact = [0 for i in range(1,1000005)]
count = [0 for i in range(1,1000005)]
mark = [False for i in range(1,1000005)]
def new_prime():
	for i in range(2,1000002,1):
		if(mark[i]==False):
			for j in range(i,1000002,i):
				if(mark[j]==False):
					mark[j] = True
					fact[j] = i
				#print fact[j]
	return
    
new_prime()
for i in range(1,1000002,1):
	count[i]=0
for i in range(1,1000001,1):
	count[fact[i]]+=1
	#print fact[i]
kases = int(input())
for kase in range(kases):
    N = int(input())
    #print N
    print(count[N])


f = []
def populate_array():
	f = [0]*1000001
	c = [0]*1000001
	ctr = 0
	for i in range(2,1000001,2):
		f[i] = 2
		ctr += 1
	c[2] = ctr
	#print ctr
	for i in range(3,1000001,2):
		if f[i] == 0 :
			ctr = 0
			for j in range(i,1000001,i):
				if f[j] == 0:
					f[j] = i
					ctr += 1
			c[i] = ctr
	return c


t = int(input())
primes = populate_array()
while t>0:
	n = int(input())
	print(primes[n])
	t -= 1