A greek once sifted some numbers. And it did something wonderful!

-----Input:-----
- First line will contain an integer $N$

-----Output:-----
Output in a single line answer to the problem.

-----Constraints-----
- $1 \leq N \leq 10^5$

-----Sample Input 1:-----
10

-----Sample Output 1:-----
4

-----Sample Input 2:-----
20

-----Sample Output 2:-----
8

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
try:

	def isPrime(n):
		if n <= 1:
			return False
		for i in range(2, n):
			if n % i == 0:
				return False
		return True

	def printPrime(n):
		count = 0
		for i in range(2, n + 1):
			if isPrime(i):
				count = count + 1
		print(count)
	n = int(input())
	printPrime(n)
except:
	pass


count = 0

def SieveOfEratosthenes(n):
	nonlocal count
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			count += 1
SieveOfEratosthenes(int(input()))
print(count)


a = int(input())
b = 0
for x in range(1, a + 1):
	c = 0
	for y in range(1, x):
		if x % y == 0:
			c = c + 1
	if c == 1:
		b = b + 1
print(b)


l = []

def isPrime(n):
	if n <= 1:
		return False
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
for _ in range(1, int(input()) + 1):
	if isPrime(_):
		l.append(_)
	else:
		pass
print(len(l))


from math import ceil

def is_prime(x):
	if x == 2:
		return True
	for i in range(2, ceil(x ** 0.5) + 1):
		if x % i == 0:
			return False
	return True
count = 0
n = int(input())
for i in range(2, n + 1):
	if is_prime(i):
		count += 1
print(count)


import math
number = int(input())
primes = []
for i in range(2, number + 1):
	primes.append(i)
i = 2
while i <= int(math.sqrt(number)):
	if i in primes:
		for j in range(i * 2, number + 1, i):
			if j in primes:
				primes.remove(j)
	i = i + 1
print(len(primes))


N = int(input())
primes = 0
for i in range(2, N + 1):
	flag = 1
	for a in range(2, i // 2 + 1):
		if i % a == 0:
			flag = 0
			break
	if flag:
		primes += 1
print(primes)


def count_Primes_nums(n):
	ctr = 0
	for num in range(n + 1):
		if num <= 1:
			continue
		for i in range(2, num):
			if num % i == 0:
				break
		else:
			ctr += 1
	return ctr
try:
	n = int(input())
	print(count_Primes_nums(n))
except:
	pass


try:
	c = 0
	n = int(input())
	for i in range(1, n + 1):
		cu = 0
		for j in range(1, i + 1):
			if i % j == 0:
				cu += 1
		if cu == 2:
			c += 1
	print(c)
except:
	pass


count = 0
for val in range(int(input()) + 1):
	if val > 1:
		for n in range(2, val):
			if val % n == 0:
				break
		else:
			count += 1
print(count)


n = int(input())
c = 0
for i in range(2, n + 1):
	f = 0
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			f = 1
			break
	if f == 0:
		c = c + 1
print(c)


n = int(input())
c = 0
for i in range(1, n + 1):
	if i > 1:
		for a in range(2, i):
			if i % a == 0:
				break
		else:
			c += 1
print(c)


def prime_eratosthenes(n):
	prime_list = []
	z = []
	for i in range(2, n + 1):
		if i not in prime_list:
			z.append(i)
			for j in range(i * i, n + 1, i):
				prime_list.append(j)
	print(len(z))
x = int(input())
prime_eratosthenes(x)


start = 1
c = 0
end = int(input())
l = []
for val in range(start, end + 1):
	if val > 1:
		for n in range(2, val):
			if val % n == 0:
				break
		else:
			c += 1
print(c)


try:

	def isPrime(n):
		if n <= 1:
			return False
		for i in range(2, n):
			if n % i == 0:
				return False
		return True

	def printPrime(n):
		l1 = []
		for i in range(2, n + 1):
			if isPrime(i):
				l1.append(i)
		print(len(l1))

	def __starting_point():
		n = int(input())
		printPrime(n)
except:
	pass
__starting_point()


n = int(input())
count = 0
c = 0

def prime(n):
	c = 0
	for i in range(1, n + 1):
		if n % i == 0:
			c = c + 1
	if c == 2:
		return 1
	else:
		return 0
count = 0
for i in range(1, n + 1):
	count = count + prime(i)
print(count)


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
c = 0
for i in range(1, n + 1):
	if isPrime(i):
		c = c + 1
print(c)


MAX = 10000
prefix = [0] * (MAX + 1)

def buildPrefix():
	prime = [1] * (MAX + 1)
	p = 2
	while p * p <= MAX:
		if prime[p] == 1:
			i = p * 2
			while i <= MAX:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, MAX + 1):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def query(L, R):
	return prefix[R] - prefix[L - 1]
buildPrefix()
L = 1
R = int(input())
print(query(L, R))


from sys import stdin, stdout

def main():
	cases = stdin.readline()
	n = int(cases)
	if n == 0:
		print(n)
		return
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	count = 0
	for i in prime:
		if i == True:
			count += 1
	print(count)

def __starting_point():
	main()
__starting_point()