Hi everyone,
I’m having a problem in the running time of my code in Python 3.7, I have done it with two versions and for both of them the problema is the runtime. I hope someone could tell me how to improve my code so I can fix that problem.
This is the first code I tried:
def PrimerNum(start,limit):
primes = []
for i in range(start, limit+1):
count = 0
for j in range(1,i+1):
if i%j == 0:
count += 1
if count == 2:
primes.append(i)
return primes
t = int(input())
if t <= 10:
for i in range(t):
m = int(input())
n = int(input())
if 1<=m<=n<=100000000 and n-m<=100000:
x = PrimerNum(m,n)
print(x)
After this version I tried using Sieve of Eratosthenes and it happened the same, runtime error. This is the code:
def SieveOfEra(m,n):
num = [True for i in range(n+1)]
p = 2
while (p*p<=n):
if (num[p] == True):
for i in range(p*p, n+1, p):
num[i] = False
p = p+1
if m == 1:
for p in range(2,n+1):
if num[p] == True:
print(p)
else:
for p in range(m,n+1):
if num[p] == True:
print(p)
t = int(input())
if t <= 10:
for i in range(t):
m = int(input())
n = int(input())
if 1<=m<=n<=100000000 and n-m<=100000:
SieveOfEra(m,n)`Preformatted text`
created
last reply
- 3
replies
- 709
views
- 2
users
- 1
like
- 1
link