[Python] Python: Solution with pre-generated list of primes[Python] Python: Solution with pre-generated list of primes
🧮
Primes
Week 8, 2026
def main() -> None:
maximum = 10000 # input of program
primes = get_primes(maximum**2 + 1)
difference = 0
MinusOneCount = 0
AddOneCount = 0
for num in range(1, maximum+1):
n = num**2 - 1
if search(n, primes):
print(f"{num}^2 - 1 = {n}")
print(f"Difference: {num - difference}")
print()
difference = num
MinusOneCount += 1
n = num**2 + 1
if search(n, primes):
print(f"{num}^2 + 1 = {n}")
print(f"Difference: {num - difference}")
print()
difference = num
AddOneCount += 1
print("--- Counts ---")
print()
print(f"MinusOneCount: {MinusOneCount}")
print(f"AddOneCount: {AddOneCount}")
def get_primes(n: int) -> list[int]:
ns = []
primes = []
ns.append(2)
for i in range(3, n + 1, 2): ns.append(i)
n = len(ns)
for i in range(1, n):
if ns[i] != 0:
b = ns[i]
a = b * 2
while ((b + a) - 1) // 2 < n:
b += a
ns[(b - 1) // 2] = 0
for i in range(n - 1):
if ns[i] != 0:
primes.append(ns[i])
return primes
def search(num: int, primes: list[int]) -> bool:
a = 0
b = len(primes) - 1
while True:
i = int((a + b) / 2)
if num > primes[i]:
a = i
elif num < primes[i]:
b = i
else:
return True
if b - a == 1:
if num == primes[a] or num == primes[b]:
return True
return False
main()
