import math
import time

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)
	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)+len(liste2)))
	print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
	print("> Estimation Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
	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):
	# INITIALISATION
	start_time = time.time()
	nombres = n*[1]
	nombres[0] = 0
	p = eratostene(math.sqrt(2*n))
	lenp = len(p)
	r = []
	print("Crible G: Initialisation: %s seconds ---" % (time.time() - start_time))

	# CRIBLAGE DES NOMBRES
	start_time = time.time()
	for i in range(lenp):
		r.append(2*n % p[i])
		j = r[i]
		while j <= n:
			nombres[j-1] = 0
			j += p[i]
	print("Crible G: Criblage des entiers 1 à n: %s seconds ---" % (time.time() - start_time))

	# EXTRACTION DES NOMBRES PREMIERS
	start_time = time.time()
	premiers = []
	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)
	print("Crible G: Extraction premiers n à 2*n: %s seconds ---" % (time.time() - start_time))
	return premiers


def fam_reste(reste, p8):
	i = 0
	while i < 8 and reste % 30 != p8[i]:
		i += 1
	if i == 8:
		return -1
	else:
		return i


# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 15
def crible_G2(n):
	# INITIALISATION
	start_time = time.time()
	nbcell = int(n/30)
	nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
	p = eratostene(math.sqrt(2*n))
	p = p[3:]
	lenp = len(p)
	r = []
	p8 = [1, 7, 11, 13, 17, 19, 23, 29]
	pfam = []
	print("Crible mod 30: Initialisation: %s seconds ---" % (time.time() - start_time))

	# FAMILLES POUR CHAQUE Pi
	start_time = time.time()
	for i in range(lenp):
		r.append(2*n % p[i])
		pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
		j = r[i]
		incr = p[i]*2
		d_c = str(j)[-1]
		# On elimine les restes pairs
		if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
			j += p[i]
			d_c = str(j)[-1]
		while j < n:
			if d_c == '5' or j % 3 == 0:  # on passe au suivant
				fam = -1
			elif d_c == '1':  # on vérifie 1 et 11
				if j % 30 == p8[0]:
					fam = 0
				else:
					fam = 2
			elif d_c == '3':  # on vérifie 13 et 23
				if j % 30 == p8[3]:
					fam = 3
				else:
					fam = 6
			elif d_c == '7':  # on vérifie 7 et 17
				if j % 30 == p8[1]:
					fam = 1
				else:
					fam = 4
			else:  # on vérifie 19 et 29 (d_c = 9)
				if j % 30 == p8[5]:
					fam = 5
				else:
					fam = 7
			if fam != -1 and pfam[i][fam] == 0:
				pfam[i][fam] = j
			j += incr
			d_c = str(j)[-1]

	print("Crible mod 30: Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

	# ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
	start_time = time.time()
	lenpfam = len(pfam)
	for i in range(lenpfam):
		for j in range(8):
			index = int((pfam[i][j] - p8[j]) / 30)
			while index < nbcell:
				nombres[j][index] = 0
				index += p[i]
	print("Crible mod 30: Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

	# AFFICHAGE
	for i in range(8):
		count = 0
		for cell in nombres[i]:
			if cell == 1:
				count += 1

	# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
	start_time = time.time()
	premiers = []
	for i in range(8):
		for j in range(nbcell-1, -1, -1):
			if nombres[i][j] == 1:
				premier = 2*n-((j*30)+p8[i])
				premiers.append(premier)
	print("Crible mod 30: Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
	premiers.sort()
	return premiers


n = int(input("Donnez la valeur de N = 30k: "))
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(n))
print("On a "+str(nb)+" nombres premiers")
input()