Problem:
Chebyshev's Theorem    If n is a positive integer,
there exists at least one prime number greater than n and less than or equal to 2 n .
This fact is known as Chebyshev's theorem or the Bertrand-Chebyshev theorem,
which had been conjectured by Joseph Louis François Bertrand (1822–1900)
and was proven by Pafnuty Lvovich Chebyshev (Пафнутий Львович Чебышёв, 1821–1894) in 1850.
Srinivasa Aiyangar Ramanujan (1887–1920) gave an elementary proof in his paper published in 1919.
Paul Erdős (1913–1996) discovered another elementary proof in 1932.    For example, there exist 4 prime numbers greater than 10 and less than or equal to 20, i.e. 11, 13, 17 and 19.
There exist 3 prime numbers greater than 14 and less than or equal to 28, i.e. 17, 19 and 23.    Your mission is to write a program that counts the prime numbers greater than n and less than or equal to 2 n for each given positive integer n .
Using such a program, you can verify Chebyshev's theorem for individual positive integers.   Input   The input is a sequence of datasets.
A dataset is a line containing a single positive integer n .
You may assume n ≤ 123456.    The end of the input is indicated by a line containing a single zero.
It is not a dataset.   Output   The output should be composed of as many lines as the input datasets.
Each line should contain a single integer and should never contain extra characters.    The output integer corresponding to a dataset consisting of an integer n should be the number of the prime numbers p satisfying n < p ≤ 2 n .   Sample Input  1
10
13
100
1000
10000
100000
0  Output for the Sample Input  1
4
3
21
135
1033
8392

Solution (Python):



MAX = 250000
SQRT = 500     

prime = [True]*MAX
def sieve():
	for i in range(2, MAX, 2): prime[i] = False
	for i in range(3, SQRT, 2):
		if prime[i]:
			for j in range(i*i, MAX, i): prime[j] = False
			
sieve()
while True:
	n = int(input())
	if n == 0: break
	ans, m = 0, n << 1
	if n == 1: ans += 1         
	i = n + 1
	if (i&1) == 0: i += 1       
	while i <= m:
		if prime[i]: ans += 1
		i += 2
	print(ans)

Solution (Python):



from bisect import bisect_left

MAX = 250000
SQRT = 500     

f = [True]*MAX
prime = [2]
def sieve():

	for i in range(3, SQRT, 2):
		if f[i]:
			for j in range(i*i, MAX, i): f[j] = False
	for i in range(3, MAX, 2):
		if f[i]: prime.append(i)
			
sieve()
while True:
	n = int(input())
	if n == 0: break
	if n == 1: print(1)
	else:
		a = bisect_left(prime, n<<1)
		if prime[a] != n<<1: a -= 1
		print(a-bisect_left(prime, n+1, 0, a)+1)

Solution (Python):



from bisect import bisect_left

MAX = 250000
SQRT = 500     

f = [True]*MAX
prime = [2]
def sieve():

	for i in range(3, MAX, 2):
		if f[i]:
			prime.append(i)
			for j in range(i*i, MAX, i): f[j] = False
			
sieve()
while True:
	n = int(input())
	if n == 0: break
	if n == 1: print(1)
	else : print(bisect_left(prime, n<<1)-bisect_left(prime, n+1))

Solution (Python):
prime_num = [1 for i in range(300000)]
prime_num[0] = 0
prime_num[1] = 0
i = 2
j = 0
while i < len(prime_num):
    if prime_num[i]:
        j = i * 2
        while j < len(prime_num):
            prime_num[j] = 0
            j += i
    i += 1


ans_list = []

while True:
    n = int(input())
    if n == 0:
        break
    ans = 0
    for i in range(n + 1, 2 * n + 1):
        if prime_num[i]:
            ans += 1
    ans_list.append(ans)

for i in ans_list:
    print(i)

Solution (Python):
def get(num):
    n=0
    is_prime=[0]*300050
    for i in range(0,num+1):
        is_prime[i]=True
    is_prime[0]=is_prime[1]=False
    for i in range(2,num+1):
        if(is_prime[i]):
            n+=1
            for j in range(2*i,num+1,i):
                is_prime[j]=False
    return n

while True:
    a=map(int,raw_input().strip().split())
    b=a[0]
    if(b==0):
        break
    p=get(2*b)-get(b)





    print(p)

Solution (Python):
def sosu(n):
    s = [1] * (n+1)
    s[0] = s[1] = 0
    
    end = int(n ** 0.5) + 1
    for i in range(2,end+1):
        if s[i] == 0:continue
        j = i+i
        while j <= n:
            s[j] = 0
            j += i

    return s

S = sosu(123456*2)

while 1:
    n = int(input())
    if not n:break
    print(len([v for v in S[n+1:n*2+1] if v == 1]))

Solution (Python):


import math

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

primeTable = sieve_of_erastosthenes((10**6))

while True:
    n = int(input())
    if n == 0:
        break
    print(sum([1 if primeTable[i] == True else 0 for i in range(n+1,2*n+1)]))

Solution (Python):
import math
MAX = 123456
def sieve (n):
	prime = [0,0]
	prime += [1 for i in range(n-1)]
	ub = math.sqrt(n) + 1
	d = 2
	while d <= ub:
		if prime[d] == 0:
			d += 1
			continue
		prod = 2
		while d * prod <= n:
			prime[d*prod] = 0
			prod += 1
		d += 1
	return prime
prime = sieve(2 * MAX)
while 1:
	n = int(raw_input())
	if n == 0:
		break
	print sum(prime[n+1:2*n+1])

Solution (Python):



P = [0]*(123456*2+1)
for i in range(2, 123456*2+1):
    if P[i]==0:
        j = i
        for j in range(i+i, 123456*2+1, i):
            P[j] = 1

n = int(raw_input())
while n!=0:
    cnt = 0
    for i in range(n+1, 2*n+1):
        if P[i] == 0:
            cnt += 1
    print cnt

    n = int(raw_input())

Solution (Python):
from math import sqrt

size = 123456
primes = [x for x in range(2, 2*size+1) if x == 2 or x % 2 == 1]
for i in range(2, int(sqrt(2*size))):
    primes = [x for x in primes if x % i != 0 or x == i]

while True:
    n = int(input())
    if n == 0: break
    nums = [x for x in primes if x > n and x <= 2*n]
    print(len(nums))

Solution (Python):
def main():
    e = [True for i in range(2*123456+1)]
    e[0] = e[1] = False
    i = 2
    while i*i <= 2*123456:
        for j in range(2*i, 2*123456+1, i):
            e[j] = False
        i += 1
    while True:
        n = int(input())
        if n == 0:
            exit()
        print(e[n+1:2*n+1].count(True))

if __name__ == '__main__':
    main()

Solution (Python):

p = [True] * (123456*2)
p[0] = p[1] = False
for i in range(2, int(len(p)**0.5)+1):
	if p[i]:
		for j in range(i*2, len(p), i):
			p[j] = False

while True:
	n = int(input())
	if n == 0:
		break
	print(p[n+1:n*2+1].count(True))

Solution (Python):



import array




def sieve_of_eratosthenes(limit, typecode="L"):
    
    
    table = array.array("B", (True for i in range(limit)))
    
    table[0] = False
    table[1] = False
    
    
    for i in range(2, limit):
        if table[i]:  
            
            for j in range(i * 2, limit, i):  
                table[j] = False  
    
    return table


if __name__ == "__main__":
    table = sieve_of_eratosthenes(123456 * 2 + 1)
    while True:
        n = int(input())
        if n == 0:
            break
        else:
            print(sum(table[n + 1: 2 * n + 1]))

Solution (Python):


def isPrime(n):
    if n <= 1:
        return False 
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    i = 3
    while i * i <= n :
        if n % i == 0:
            return False 
        i += 1

    return True        


while True:
    n = input()
    if n == 0:break

    ans = 0
    for i in range(n + 1, n * 2 + 1):
        if isPrime(i):ans += 1

    print ans

Solution (Python):
while True:
    n = int(input())
    if not(n): break
    flag = [True]*(n*2+1)
    flag[0] = flag[1] = False
    for i in range(2,int(n*2**0.5)+1):
        if flag[i]:
            for j in range(i**2, n*2+1, i):
                flag[j] = False
    print(flag[n+1:].count(True))

Solution (Python):


while True:
    n = int(raw_input())
    if n == 0:
        break
    l = range(0, 2*n + 1)
    l[0] = 0
    l[1] = 0
    for i in range(0, 2*n + 1):
        if l[i] != 0:
            for k in range(i + i, 2*n + 1, i):
                l[k] = 0
            continue
    l = l[n + 1:]
    l = [x for x in l if x]
    print len(l)

Solution (Python):
def prime(n):
    flag = [True]*(n+1)
    flag[0] = flag[1] = False
    for i in range(2,int(n**0.5)+1):
        if flag[i]:
            for j in range(i**2, n+1, i):
                flag[j] = False
    return flag
flag = prime(123456*2)
while True:
    n = int(input())
    if n==0: break
    print(flag[n+1:2*n+1].count(True))

Solution (Python):
m=246912
p=[1]*m
p[0]=p[1]=0
for i in range(2,int(m**0.5)+1):
    if p[i]:
        for j in range(i*i,m,i):
            p[j]=0
while 1:
    n=int(input())
    if n==0:break
    print(sum(p[n+1:2*n+1]))

Solution (Python):
prime = [True] * (123456 * 2 + 1)
prime[0] = prime[1] = False
for i in range(2, int(len(prime) ** 0.5) + 1):
    if prime[i]:
        for j in range(i * 2, len(prime), i):
            prime[j] = False
prinum = [0] * len(prime)
for i in range(1, len(prime)):
    prinum[i] = prinum[i - 1] + prime[i]

while True:
    n = int(input())
    if n == 0:
        break
    print(prinum[2 * n] - prinum[n])

Solution (Python):
prilen = 123456 * 2 + 1
prime = [True] * prilen
prime[0] = prime[1] = False
for i in range(2, int(prilen ** 0.5)):
    if prime[i]:
        for j in range(i * 2, prilen, i):
            prime[j] = False
            
prinum = [0] * prilen
for i in range(1, prilen):
    prinum[i] = prinum[i - 1] + prime[i]

while True:
    n = int(input())
    if n == 0:
        break
    print(prinum[2 * n] - prinum[n])

Solution (Python):
primes = [0, 0] + [1]*246911
for i in range(2, 497):
    if primes[i]:
        for j in range(i*i, 246913, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    print(sum(1 for i in range(n+1, 2*n+1) if primes[i]))

Solution (Python):
import sys
from itertools import accumulate

limit = 2 * 123456 + 1

def solve():
    is_prime = eratos(limit)
    cnt = [0] + list(accumulate(is_prime))

    while 1:
        n = int(sys.stdin.readline().rstrip())

        if n == 0:
            return

        ans = cnt[2*n + 1] - cnt[n + 1]

        print(ans)

def eratos(n):
    sieve = [True] * n
    sieve[0] = sieve[1] = False

    for p in range(2, n):
        if p*p > n:
            break
        if sieve[p]:
            for q in range(p*p, n, p):
                sieve[q] = False

    return sieve

if __name__ == '__main__':
    solve()

Solution (Python):
input_list = []

while True:
    N = int(input())
    if N == 0:
        break
    input_list.append(N)

n = 123456*2
isPrime = [True for i in range(n)]

for i in range(int(n)):
    if i % 2 != 0:
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                isPrime[i] = False
                break
    else:
        isPrime[i] = False

isPrime[2] = True


while input_list:
    tmp = input_list.pop(0)
    tmp_isPrime = isPrime[tmp+1: tmp*2+1]
    print(tmp_isPrime.count(True))

Solution (Python):
while 1:
    n = int(input())
    if n ==0 :break
    e = [1 for _ in range(2*n+1)]
    for i in range(2,n+1):
        if e[i] == 1:
            for j in range(2,int(2*n/i) + 1):
                e[i*j] = 0
    print(sum(e[n+1:2*n+1]))

Solution (Python):
while 1:
    n = int(input())
    if n ==0 :break
    e = [1 for _ in range(2*n+1)]
    for i in range(2,n+1):
        if i *i >n:pass
        if e[i] == 1:
            for j in range(2,int(2*n/i) + 1):
                e[i*j] = 0
    print(sum(e[n+1:2*n+1]))

Solution (Python):
MAXN = 123456 * 2
sieve = [1 for i in range(MAXN+1)]
sieve[0] = sieve[1] = 0
n = 2
while n*n <= MAXN:
    if sieve[n] == 1:
        for nn in range(2*n,MAXN+1,n):
            sieve[nn] = 0
    n += 1
cums = [0]
for s in sieve:
    cums.append(cums[-1] + s)

while True:
    N = int(input())
    if N == 0: break
    ans = cums[2*N+1] - cums[N+1]
    print(ans)

Solution (Python):
import math
while 1:
	n = int(input())
	if n == 0:
		break
	count = 0
	if n == 1:
		count = 1
		x = n + 2
	elif n % 2 == 1:
		x = n + 2
	elif n == 2:
		count = 1
		x = n + 1
	else:
		x = n + 1
	for i in range(x,n*2+1,2):
		y = math.trunc(math.sqrt(i))+3
		if y % 2 == 1:
			z = y-2
		else:
			z = y-1
		for j in range(3,y,2):
			if i % j == 0:
				break
			if j == z:
				count += 1
	print count

Solution (Python):
prime = [True for i in range(250001)]
prime[0] = prime[1] = False
for i in range(2, 500):
    if prime[i]:
        for j in range(2, 250000 // i + 1):
            prime[i * j] = False

while True:
    n = int(input())
    if n == 0:
        break
    print(prime[n + 1 : n * 2 + 1].count(True))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Prime():
    def __init__(self, n):
        self.N = n = n + 1
        self.A = a = [True] * n
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(n)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,n+1,i):
                a[j] = False
        self.RUI = rui = [0] * n
        for i in range(2,n):
            if a[i]:
                rui[i] = rui[i-1] + 1
            else:
                rui[i] = rui[i-1]

    def is_prime(self, n):
        return self.A[n]

    def cnt(self, a, b):
        return self.RUI[b] - self.RUI[a]

def main():
    rr = []

    pr = Prime(123456 * 2)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(pr.cnt(n,n*2))

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):

from bisect import bisect, bisect_left
def inpl(): return map(int, input().split())

def primes(N):
    P = []
    sieve = [1]*(N+1)
    sieve[:2] = [0]*2
    for i in range(N+1):
        if sieve[i]:
            P.append(i)
            sieve[i::i] = [0]*(N//i)
    return P

P = primes(123456*2)

N = int(input())

while N:
    l = bisect(P, N)
    r = bisect(P, 2*N)-1
    print(r-l+1)
    N = int(input())

Solution (Python):


from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

N = 250000

isprime = [False, False] + [True for i in range(N)]

for i in range(N):
    if isprime[i]:
        for j in range(i * 2, N, i):
            isprime[j] = False

for i in range(1, N):
    isprime[i] += isprime[i - 1]

while True:
    n = input()
    if n == 0:
        break
    print isprime[2 * n] - isprime[n]

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

sosuu = [False,False] + [True for i in range(300000)]

for i in range(300000):
	if sosuu[i]:
		for j in range(i**2,300000,i):
			sosuu[j] = False
ruisekiwa = [0,0]
for i in range(2,300000):
	if sosuu[i]:
		ruisekiwa.append(ruisekiwa[i-1]+1)
	else:
		ruisekiwa.append(ruisekiwa[i-1])

def main():
	n = int(input())
	if n == 0:
		return
	print(ruisekiwa[2*n]-ruisekiwa[n])
	main()
	return
main()

Solution (Python):

list_n = [True for i in range(123456*2+1)]
list_n[0] = False
list_n[1] = False
ans = []
count = 0
for i, n in enumerate(list_n):
    if n:
        prime = i
        count += 1
        k = prime * 2
        l = 3
        while k < 123456*2+1:

            list_n[k] = False
            k = prime * l
            l += 1
    ans.append(count)
a = 1

while True:
    try:
        N = int(input())
        if N == 0:
            break
        count = ans[2*N] - ans[N]
        print(count)
    except:
        break

Solution (Python):
import sys

MAX = 2500000
prime = [-1] * MAX
i = 2
while MAX > i:
	if prime[i - 1] == -1:
		prime[i - 1] = 0
		temp = i * 2
		while temp < MAX:
			prime[temp - 1] = 1
			temp += i
	if i == 2:
		i += 1
	else:
		i += 2

while True:
    n = int(sys.stdin.readline())
    
    if n == 0:
        break

    count = 0
    for i in xrange(n + 1,  2 * n + 1):
        if prime[i - 1] == 0:
            count += 1
    print count

Solution (Python):
import math
import bisect
N=123456*2
prime=[True]*(N+1)
prime[0],prime[1]=False,False
for i in range(2,int(math.sqrt(N))):
    if prime[i]==True:
        j=i
        while i*j<=N:
            prime[i*j]=False
            j+=1
prime=[i for i in range(N+1) if prime[i]==True]

while True:
    n=input()
    if n==0:break
    if n==1:
        print 1
    else:
        l=bisect.bisect_left(prime,n+1)
        u=bisect.bisect_left(prime,2*n)
        print u-l

Solution (Python):
r = 2*123456+1
s = int(r**0.5)
p = [1]*r
p[0] = p[1] = 0
for i in range(s):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]

while 1:
	n = input()
	if n == 0: break
	print sum(p[n+1:2*n+1])

Solution (Python):
import math
def kosu(n):
    l =[]
    sosu = [True] * (n+1)
    sosu[0] = False
    sosu[1] = False
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if not sosu[i]:
            continue
        for j in range(i*2,n+1,i):
            sosu[j] = False
    for i in range(len(sosu)):
        if sosu[i]:
            l.append(i)
    return(l)
        
while True:
    n = int(input())
    if n == 0:
        break
    ans = len(kosu(2*n)) - len(kosu(n))
    print(ans)

Solution (Python):
import math
import bisect

inputs = []
while True:
    n = int(input())
    if n == 0:
        break
    inputs.append(n)
    
max_n = max(inputs)

primes = [True for i in range(2 * max_n + 1)]
primes[0] = False
primes[1] = False
for i in range(2, int(math.sqrt(2 * max_n)) + 1):
    tmp = 2 * i
    while tmp <= 2 * max_n:
        primes[tmp] = False
        tmp += i

primes_lst = []
for i in range(2 * max_n + 1):
    if primes[i]:
        primes_lst.append(i)
        
for n in inputs:
    if n == 1:
        print(1)
    else:
        print(bisect.bisect_left(primes_lst, 2 * n) - bisect.bisect_right(primes_lst, n))

Solution (Python):

import sys
import math

sys.setrecursionlimit(10000000)



def count_prime(N):
    N = N*2
    max = int(math.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


while True:
    target = int(input())
    if target == 0 :
        break

    prime_list = count_prime(target)

    print(sum(2*target>=x for x in prime_list) - sum(target>=x for x in prime_list))

Solution (Python):



MAX = 1000000
s = [1] * MAX
s[0] = 0
s[1] = 0

start = 2
while True:
    pmb = 0
    for i in range(start, MAX):
        if s[i] == 1:
            pmb = i
            break

    if pmb == 0:
        break 
    for i in range(pmb ** 2, MAX, pmb):
        s[i] = 0 

    start += 1

while True:
   n = int(input())
   if n == 0: break
        
   c = 0
   for i in range(n + 1, n + n + 1):
      if s[i] == 1:
         
         c += 1
   print(c)

Solution (Python):
import math
def isprime(x):
    if x==2:
        return 1
    elif x<2 or x%2==0:
        return 0
    else :
        i=3
        while i<=math.sqrt(x):
            if x%i==0:
                return 0
            i=i+2
        return 1

while True:
    n=int(input())
    if n==0:
        break
    ans=0
    for i in range(n+1,2*n+1):
        if isprime(i)==1:
            ans+=1
    print(ans)

Solution (Python):
import math
def sosu(x):
    if x == 1:
        return False
    for i in range (2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

while True:
    n = int(input())
    if n == 0:
        break
    a = []
    for i in range(n+1, 2*n+1):
        if sosu(i):
            a.append(i)
    print(len(a))

Solution (Python):
import math
def sosu(n):
    if n == 1:
        return 1
    for k in range(2,int(math.floor(math.sqrt(n)))+1):
        if n%k == 0:
            return 1
    return 0
    
while True:
    n = int(input())
    
    if n == 0:
        break
    
    a = 0
    for i in range(n+1,2*n+1):
        if sosu(i) == 0:
            a += 1
    print(a)

Solution (Python):
import math
def Sosu(N) :
    if N == 1 :
        return False
    else :
        for i in range(2, int(math.sqrt(N))+1) :
            if N % i == 0 :
                return False
        return True
    

def amount_sosu(a, b) :
    ans = 0
    for i in range(a+1, b+1) :
        if Sosu(i) :
            ans += 1
    return ans

while True :
    n = int(input())
    if n == 0 :
        break
    
    print(amount_sosu(n, n*2))

Solution (Python):
import math
def prime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i == 0:
            return 0
    return 1

while True:
    n = int(input())
    
    if n==0:
        break
    
    n2 = 2*n
    
    num = list(range(n+1,n2+1))
    count = 0
    for i in range(len(num)):
        x = num[i]
        if prime(x):
            count += 1
    print(count)

Solution (Python):
P = [1 for i in range(250000)]


P[0] = 0
P[1] = 0

for i in range(2, 250000) :
    for j in range(2, 250000 // i) :
        P[i * j] = 0
        
        
while True :
    n = int(input())
    
    if n == 0 :
        break
    
    else :
        print(P[n + 1 : 2 * n + 1].count(1))

Solution (Python):
y = [True for i in range(250001)]
y[0] = y[1] = False
for i in range(2, 500):
    if y[i]:
        for j in range(2, 250000 // i + 1):
            y[i * j] = False
while True:
    n = int(input())
    if n == 0:
        break
    print(y[n + 1 : n * 2 + 1].count(True))

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

while 1:
    n = int(input())
    if n == 0:
        break
    ans_1 = len(primes(2*n))
    ans_2 = len(primes(n))
    print(ans_1-ans_2)

Solution (Python):
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


while 1:
    n = int(input())
    if n==0: break
    cnt = 0
    for i in range(n+1, 2*n+1):
        if is_prime(i):
            cnt += 1
    print(cnt)

Solution (Python):





from sys import stdin,setrecursionlimit


setrecursionlimit(10**6)
input=stdin.readline
prime=[True]*300000
prime[0]=False
prime[1]=False
for i in range(2,int(300000**0.5)+1):
    if prime[i]:
        for j in range(i*2,300000,i):
            prime[j]=False
while 1:
    n=int(input().rstrip())
    if n==0:
        break
    cnt=0
    for i in range(n+1,n*2+1):
        if prime[i]:
            cnt+=1
    print(cnt)

Solution (Python):
m = 246912
p = [1] * m
p[0] = p[1] = 0
for i in range(2, int(m**0.5) + 1):
  if p[i]:
    for j in range(i*i, m, i):
      p[j] = 0
while True:
  n = int(input())
  if n == 0:
    break
  print(sum(p[n+1:2*n+1]))

Solution (Python):
ans_list = []

def sieve(N):
    global table,prime
    table = [True]*(N+1)
    table[0] = False
    table[1] = False
    prime = []
    for i in range(2,N+1):
        if table[i]:
            prime.append(i)
            for j in range(2*i,N+1,i):
                table[j] = False

sieve(123456*2)

while True:
    n = int(input())
    if n == 0:
        break
    ans = 0
    for p in prime:
        if n < p <= 2*n:
            ans += 1
    ans_list.append(ans)
    
for ans in ans_list:
    print(ans)

Solution (Python):
def prime(n):
    for i in range(2,int((n)**0.5)+1):
        if n % i == 0:
            return False
    return True

def main(n):
    ans = 0
    for i in range(n+1,2*n+1):
        if prime(i):
            ans += 1
    print(ans)
while 1:
    n = int(input())
    if n == 0:
        break
    main(n)

Solution (Python):


N = (123456*2)+1
p = [1] * N

def seive():
    for i in range(2, int(N ** 0.5)+1):
        if p[i] == 1:
            for j in range(i*2, N+1, i):
                p[j] = 0
seive()

def main():
    while True:
        n = int(input())
        if n == 0: break
        print(sum(p[n+1: n*2+1]))

main()

Solution (Python):
"チェビシェフの定理"


def eratostenes(n):
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0
    for i in range(2, int(n**(1/2))):
        if primes[i] == 0:  
            continue
        else:
            for j in range(i*2, n+1, i):
                primes[j] = 0
    return primes


primes = eratostenes(250000)

while True:
    N = int(input())
    if N == 0:
        break
    print(sum(primes[N+1:2*N+1]))

Solution (Python):
def dfs(k):
    if k==1:
        return 0
    elif k==2:
        return 1
    for i in range(2,int(k**0.5+1)):
        if k%i==0:
            return 0
    return 1
while True:
    n=int(input())
    if n==0:break
    ans=0
    for j in range(n+1,2*n+1):
        ans+=dfs(j)
    print(ans)

Solution (Python):
from math import floor

def prime(n):
    sup = floor(pow(n,1/2))
    for d in range(2,sup+1):
        if n % d == 0:
            return False
    return True

ans_list = []

def solve():
    n = int(input())
    if n == 0:
        return "end"
    cnt = 0
    for k in range(n+1,2*n+1):
        if prime(k):
            cnt += 1
    return cnt

while True:
    ans = solve()
    if ans == "end":
        break
    ans_list.append(ans)

for ans in ans_list:
    print(ans)

Solution (Python):
p = [1 for i in range(300000)]
p[0] = 0
p[1] = 0
for i in range(2, 300000): 
  j = i
  i += j
  while(i < 300000):
    p[i] = 0
    i += j

while True:
  n = int(input())
  if n == 0:
     break
  cnt = 0
  for i in range(n + 1, 2 * n + 1):
    if p[i] == 1:
      cnt += 1
  print(cnt)

Solution (Python):

MAX = 123456 * 2
prime = [True] * (MAX+1)
count = [0] * (MAX+1)
tmp = 0
prime[0] = False
prime[1] = False
for i in range(2, MAX+1):
    if prime[i]:
        tmp += 1
        for j in range(i * 2, MAX+1, i):
            prime[j] = False
    count[i] = tmp


while True:
    n = int(input())
    if n == 0:
        break
    print(count[n * 2] - count[n])

Solution (Python):
while True:
  n = int(input())
  if n==0:
    break
  ans = 2*n-n
  for x in range(n+1,2*n+1):
    for i in range(2,int(x**0.5)+1):
      if x%i==0:
        ans-=1
        break
  print(ans)

Solution (Python):
import math

def main():
    while True:
        n = int(input())
        if n == 0: break

        count = 0
        for i in range(n + 1, 2*n + 1):
            count += isprime(i)
        print(count)
    return 0

def isprime(a):
    if a == 0 or a == 1: return 0
    sq = int(math.sqrt(a))
    for i in range(2, sq + 1):
        if a % i == 0:
            return 0
    return 1
main()

Solution (Python):
import bisect
def primecheck(n):
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:return False
    prime.append(n)
    return True
def primeadd(n):
    for i in range(prime[-1]+2,2*n+2,2):
        primecheck(i)
prime=[2,3]
while 1:
    n=int(input())
    if n==0:break
    primeadd(n)
    print(bisect.bisect_left(prime,2*n+1)-bisect.bisect_left(prime,n+1))

Solution (Python):
def gen_primes(N):
    from itertools import compress
    sieve = list(range(N))
    sieve[1] = 0
    for i in range(2, int(N**.5) + 1):
        sieve[i * 2::i] = [0] * len(sieve[i * 2::i])
    return sieve


if __name__ == '__main__':
    ps = gen_primes(123456 * 2 + 1)
    for e in iter(input, '0'):
        n = int(e)
        print(sum(1 for p in ps[n + 1:2 * n + 1] if p))

Solution (Python):
table=[True for i in range(123456*2+1)]
table[0:2]=[False,False]
for i in range(2,len(table)):
    if table[i]==True and i*i<len(table):
        j=i*i
        while j<len(table):
            table[j]=False
            j+=i
while 1:
    n=int(input())
    if n==0:
        break
    ans=0
    for i in range(n+1,2*n+1):
        if table[i]==True:
            ans+=1
    print(ans)