The infinite sequence of prime numbers

[Gribouillis]

#!/usr/bin/env python # SPDX-FileCopyrightText: 2022 Member Gribouillis of www.python-forum.io # # SPDX-License-Identifier: MIT __version__ = '2022.01.28.2' from heapq import heappush, heappop, heappushpop import itertools as itt def primes(): """Return the infinite sequence of all prime numbers""" yield 2 h = [] n = 3 x, i, seq = 4, 2, itt.count(6, 2) while True: if n < x: yield n n2 = n ** 2 heappush(h, (n2, n, itt.count(n2 + n, n))) n = x + 1 x, i, seq = heappushpop(h, (next(seq), i, seq)) if __name__ == '__main__': s = primes() # print the first prime numbers for i in range(100): p = next(s) print(p)

[lucasbazan]

I made a function that verify if a number is prime, hope that is can help your code to be more tiny

def is_prime(num): mult = [i for i in range(1, num+1) if num % i == 0] if len(mult) == 2 and 1 in mult and num in mult: return True return False

https://gist.github.com/lucasbazan/9a3c4...3431c55532

[Gribouillis]

@lucasbazan How can it help?

[lucasbazan]

@lucasbazan How can it help?

If I understand correctly you can create an infinite loop with a counter using this function of mine, so I believe your code can be short. Some thing like this:

def is_prime(num): mult = [i for i in range(1, num+1) if num % i == 0] if len(mult) == 2 and 1 in mult and num in mult: return True return False def infinite_primes(): counter = 1 while True: if is_prime(counter): print(counter) counter += 1 if __name__ == '__main__': infinite_primes()

[Gribouillis]

The code is short but the performance is terrible. I modified your code to compare the two functions. Here are the results

Output:
primes(): 0.0711168740017456 seconds infinite_primes(): 55.40710521499568 seconds infinite_primes() is 779 times slower on 5000 primes.

The results rapidly get worse as the number of primes increase...

 from heapq import heappush, heappop, heappushpop import itertools as itt def primes(): """Return the infinite sequence of all prime numbers""" yield 2 h = [] n = 3 x, i, seq = 4, 2, itt.count(6, 2) while True: if n < x: yield n n2 = n ** 2 heappush(h, (n2, n, itt.count(n2 + n, n))) n = x + 1 x, i, seq = heappushpop(h, (next(seq), i, seq)) def is_prime(num): mult = [i for i in range(1, num+1) if num % i == 0] if len(mult) == 2 and 1 in mult and num in mult: return True return False def infinite_primes(): counter = 1 while True: if is_prime(counter): yield counter counter += 1 if __name__ == '__main__': from collections import deque from time import perf_counter exhaust = deque(maxlen=0).extend def perf(seq, n): start = perf_counter() exhaust(itt.islice(seq, 0, n)) return perf_counter() - start N = 5000 t1 = perf(primes(), N) print(f'primes(): {t1} seconds') t2 = perf(infinite_primes(), N) print(f'infinite_primes(): {t2} seconds') print(f'infinite_primes() is {int(t2/t1)} times slower on {N} primes.')