import math

def eratostene(n):
	n = int(n)
	m = (n-1) // 2
	b = [True]*m
	i = 0
	p = 3
	premiers = [2]
	while p*p < n:
		if b[i]:
			premiers.append(p)
			j = 2*i*i + 6*i + 3
			while j < m:
				b[j] = False
				j = j + 2*i + 3
		i += 1
		p += 2
	while i < m:
		if b[i]:
			premiers.append(p)
		i += 1
		p += 2
	return premiers


def compteInfN(liste, n):
	compte = 0
	lenListe = len(liste)
	for i in range(0, lenListe):
		if (liste[i] >= n):
			compte += 1
	return compte


def premiersNa2N(n):
	liste1 = eratostene(n*2)
	compte = compteInfN(liste1, n)
	liste2 = crible_G(n)
	print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
	# print("> N / log(2N) = " + str(n / math.log(2 * n)))
	print("> Pi(2N) = " + str(len(liste1)))
	print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
	print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
	print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
	print("> Avec eratosthene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
	print("> Avec eratosthene: On compte " + str(compte) + " nombres premiers entre "+str(n)+" et " + str(n*2))
	print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
	# print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
	# print(liste2)


def crible_G(n):
	nombres = n*[1]
	nombres[0] = 0
	p = eratostene(math.sqrt(2*n))
	lenp = len(p)
	r = []
	for i in range(lenp):
		r.append(2*n % p[i])
		j = r[i]
		while j <= n:
			nombres[j-1] = 0
			j += p[i]
	premiers = []
	print("√2N = "+str(int(math.sqrt(2*n))))
	for i in range(n-1, 0, -1):
		if nombres[i] == 1:
			premiers.append(2*n-i-1)
	# on regarde si il y a un reste égal à 1
	resteUn = 0
	lenr = len(r)
	for i in range(lenr):
		if r[i] == 1:
			resteUn = 1
	# si aucun reste n'est égal à 1 2*n-1 est premier
	if resteUn == 0:
		premiers.append(2*n-1)
	return premiers


n = int(input("Donnez la valeur de N : "))
premiersNa2N(n)
input()