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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
try:
    def isPrime(n): 
          
        # Corner case 
        if n <= 1 : 
            return False
      
        # check from 2 to n-1 
        for i in range(2, n): 
            if n % i == 0: 
                return False
      
        return True
      
    # Function to print primes 
    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

# cook your dish here
count=0
def SieveOfEratosthenes(n): 
    nonlocal count 
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    # Print all prime numbers 
    for p in range(2, n+1): 
        if prime[p]: 
            count+=1;

SieveOfEratosthenes(int(input()))
print(count)

# cook your dish here
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
#from 2 to sqrt(number)
while(i <= int(math.sqrt(number))):
    #if i is in list
    #then we gotta delete its multiples
    if i in primes:
        #j will give multiples of i,
        #starting from 2*i
        for j in range(i*2, number+1, i):
            if j in primes:
                #deleting the multiple if found in list
                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

 #cook your dish here
try:
    def isPrime(n): 
          
        # Corner case 
        if n <= 1 : 
            return False
      
        # check from 2 to n-1 
        for i in range(2, n): 
            if n % i == 0: 
                return False
      
        return True
      
    # Function to print primes 
    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

# cook your dish here
try:
    def isPrime(n): 
          
        # Corner case 
        if n <= 1 : 
            return False
      
        # check from 2 to n-1 
        for i in range(2, n): 
            if n % i == 0: 
                return False
      
        return True
      
    # Function to print primes 
    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

# cook your dish here
try:
    def isPrime(n): 
          
        # Corner case 
        if n <= 1 : 
            return False
      
        # check from 2 to n-1 
        for i in range(2, n): 
            if n % i == 0: 
                return False
      
        return True
      
    # Function to print primes 
    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

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)

# cook your dish here
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:
            #print(i)
            z.append(i)
            for j in range(i*i, n+1, i):
                prime_list.append(j)
    print(len(z))
    #print(prime_list)
x=int(input())
prime_eratosthenes(x);

# cook your dish her
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
          # l.append(val)
print(c)

try:
    def isPrime(n): 
      
    # Corner case 
        if n <= 1 : 
            return False
  
    # check from 2 to n-1 
        for i in range(2, n): 
            if n % i == 0: 
                return False
  
        return True
  
# Function to print primes 
    def printPrime(n): 
        l1=[]
        for i in range(2, n + 1): 
            if isPrime(i): 
                l1.append(i) 
    
        print(len(l1))
  
# Driver code 
    def __starting_point(): 
        n = int(input())
    # function calling 
        printPrime(n)
except:
    pass
__starting_point()

# cook your dish here
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 SieveOfEratosthenes(n): 
    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
    count = 0
    for p in range(2, n+1): 
        if prime[p]: 
            count += 1
    return count
n = int(input())
print(SieveOfEratosthenes(n))


# cook your dish here
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 isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    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)


import math

number = int(input())

primes = []
for i in range(2,number+1):
    primes.append(i)

i = 2
#from 2 to sqrt(number)
while(i <= int(math.sqrt(number))):
    #if i is in list
    #then we gotta delete its multiples
    if i in primes:
        #j will give multiples of i,
        #starting from 2*i
        for j in range(i*2, number+1, i):
            if j in primes:
                #deleting the multiple if found in list
                primes.remove(j)
    i = i+1

print(len(primes))

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)) 
 


# cook your dish here
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()