Skip to content

Instantly share code, notes, and snippets.

@primus-lab
Created January 2, 2020 08:58
Show Gist options
  • Save primus-lab/a2ee710e94c77a7d8de110c5a670bc45 to your computer and use it in GitHub Desktop.
Save primus-lab/a2ee710e94c77a7d8de110c5a670bc45 to your computer and use it in GitHub Desktop.
Prime number sieve using LCM function
# Author: Pedja
print(" ***** SIEVE *****\n\n\n")
while True:
n1=int(input("Enter lower bound : "))
n2=int(input("Enter upper bound : "))
def lcm(p,q):
p, q = abs(p), abs(q)
m = p * q
if not m: return 0
while True:
p %= q
if not p: return m // q
q %= p
if not q: return m // p
def sieve(n1,n2):
b1=2
b2=2
x=2
k=3
i=1
while x<=n2:
if i==1 and x>=n1:
print(int(x))
i=0
b3=b1+lcm(k-1,b1)
a=b3/b1-1
k=k+1
b1=b2
b2=b3
if x<a:
x=a
i=1
return ""
if n1<0:
print("Lower bound must be nonnegative number")
elif n1>n2:
print("Upper bound mustn't be less than lower bound")
else:
print(sieve(n1,n2))
try_again = ""
# Loop until users opts to go again or quit
while not(try_again == "1") and not(try_again == "0"):
try_again = input("Press 1 to try again, 0 to exit. ")
if try_again in ["1", "0"]:
continue # a valid entry found
else:
print("Invalid input- Press 1 to try again, 0 to exit.")
# at this point, try_again must be "0" or "1"
if try_again == "0":
break
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment