Python Forum
The infinite sequence of prime numbers
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
The infinite sequence of prime numbers
#1
#!/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)
Reply
#2
I made a function that verify if a number is prime, hope that is can help your code to be more tiny Big Grin

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
[Image: LEHoEPo.jpg]
Reply
#3
@lucasbazan How can it help?
Reply
#4
(Feb-11-2022, 06:27 PM)Gribouillis Wrote: @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()
[Image: LEHoEPo.jpg]
Reply
#5
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.')
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Quick prime numbers function ozs 2 3,001 May-14-2018, 08:23 AM
Last Post: ozs

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020