question-3-21

Hardy wants to test Ramanujam of his Mathematical skills. So he gives him a puzzle which is described below.

Puzzle:
There are 100 doors, numbered 1,2,....100 .Initially all doors are closed.
Now a person comes(lets call him the 1st person)he opens the first door and leaves.

Now a second guy comes and checks the status of second door(open/close) and does the following for every second door starting from door 2,
If the door is closed,open it. If the door is already open, leave it as such.
After performing the above task, he restores the second door to its initial state(open/close) and leaves.

Now this process goes on till a 100th guy, doing the same procedure ie,
The ith person checks the initial status of door numbered i, and then starting from door i, he does the following procedure to every ith door.
If the door is closed,open it. If the door is already open, leave it as such.
After performing the above task, he restores the ith door to its initial state.(open/close).

Ramanujam now tells that there is a pattern followed in the doors closed and hence he can easily,find if a door is closed or opened.
Hearing this Hardy tries to increase the difficulty of the puzzle saying that there are now 500000 doors instead of 100 and he wishes to know,
the number of doors that are closed till xth door, given x.Can you help Ramanujam solve this problem?

Input Format:
The first line contains two integers n and t,the number of doors present and the number of test cases respectively. Then t lines follow.Each line contains a single integer x.The output should correspond to the value after all 'n' people have done their work.

Output Format:
For each input test case, output a number y which indicates the number of closed doors till door numbered x.

Constraints:
1 ≤ t ≤ 100
2 ≤ n ≤ 500000
1 ≤ x ≤ n

SAMPLE INPUT
4 2
2
3

SAMPLE OUTPUT
1
2

Explanation

In the given test case,after person one, the first door alone is open.
After second person,the door numbered 2 and 4 are opened and then 2 is closed.(Initially door 2 was closed)
After person 3 , no change in the configuration as he first opens 3 and then closes 3.
After person 4, no changes as he leaves it as such.Now doors 1 and 4 are open and 2 and 3 are open.Thus for 2, the output is 1 and for 3 the output is 2, corresponding to 2,3.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def get_primes(start, stop):
	dct = {x: True for x in list(range(start, stop+1))}
	x = start

	while x ** 2 <= stop:
		if dct[x]:
			y = x ** 2
			while y <= stop:
				dct[y] = False
				y += x
		x += 1

	lst = []
	for x, y in list(dct.items()):
		if y:
			lst.append(x)

	return lst

q = input()
q = q.split()

n = int(q[0])
t = int(q[1])

for i in range(t):
	r = input()
	r = int(r)
	if r==2:
		print(1)
		continue
	ans = get_primes(2, r)
	print((len(ans)))