Sieve of Eratosthenes for primes

[guil_98]

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`

[simes]

I assume this is for PRIME1?

The problem with your first example is that you’re trying to read M and N from separate lines of input, when they should both be read from the same line. If you fix that, you’ll likely run into TLE, because your PrimerNum method is sub-optimal. To improve it, ask yourself how many test divisions do you need to do to prove that 1000000000 is not prime, and how many does the code do? Likewise, how many test divisions do you need to do to prove 999999937 is prime, and how many does the code do?

The second code has the same problem with the input format, and may also be getting a memory error when it tries to allocate an array with 1000000001 elements.

Good luck!

[guil_98]

Thanks a lot for your advices. I made the changes that you said (I guess) in the first code, but it still not working. This is the code with the changes.

def primesNumOp(start,limit):
	primes = []
	for i in range(start,limit+1):
		if 1<= i <= 7:
			count = 0
			for j in (range(1, i+1)):
				if i%j == 0:
					count+=1
			if count == 2:
				primes.append(i)
		else:
			if i%2 != 0 and i%3 != 0 and i%5 != 0 and i%7 != 0:
				primes.append(i)
	return primes

t = int(input())
if t <= 10:
	for i in range(t):
		m, n = int(input()), int(input())
		if 1<=m<=n<=100000000 and n-m<=100000:
			print(primesNumOp(m,n))

I don’t know what I’m doing wrong
Also, about the second code, how can I solve the problem of the memory, I looked for a solution but I didn’t find anything. Do you have any advice?

[simes]

Have you actually tried running this somewhere such as IDEONE? When I do, it gives a runtime error, and reports

Traceback (most recent call last):
File “./prog.py”, line 19, in
ValueError: invalid literal for int() with base 10: ‘10 20’

I think this line is the problem:

m, n = int(input()), int(input())

and needs to be replaced with something like:

m, n = [int(x) for x in input().split()]

The primesNumOp method is very odd. Why are numbers less than 7 treated differently from the others? What about composite numbers that are not divisible by 2, 3, 5 or 7?

For example, with the range 120 170, it gives

[121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169]

121, 143, and 169 are not prime. (Additionally, the numbers should be printed one per line, and you shouldn’t be printing those commas or brackets either.)

If you search this forum, you’ll find many questions about this problem, and ideas to resolve the issues you’re having.