Simple prime number generator in Python

Question

Could someone please tell me what I'm doing wrong with this code? It is just printing 'count' anyway. I just want a very simple prime generator (nothing fancy).

import math

def main():
    count = 3
    one = 1
    while one == 1:
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                continue
            if count % x != 0:
                print count

        count += 1

Treulich

Does it not terminate? Not surprising with a "while one == 1:" in it. Does it not produce any output at all? Does it produce non-prime numbers? Is it too slow? Is it not C#? What is the problem? – Jalap

If this isn't homework you might want to look into the Sieve of Eratosthenes: en.wikipedia.org/wiki/Sieve_of_Eratosthenes – Szymanski

I second CTT's comment. It will be just as easy, if not easier to code too. – Femoral

for simple implementations of Sieve of Eratosthenes see: #2068872 – Kesley

Answer 1

There are some problems:

• Why do you print out count when it didn't divide by x? It doesn't mean it's prime, it means only that this particular x doesn't divide it
• continue moves to the next loop iteration - but you really want to stop it using break

Here's your code with a few fixes, it prints out only primes:

import math

def main():
    count = 3
    
    while True:
        isprime = True
        
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break
        
        if isprime:
            print count
        
        count += 1

For much more efficient prime generation, see the Sieve of Eratosthenes, as others have suggested. Here's a nice, optimized implementation with many comments:

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}
    
    # The running integer that's checked for primeness
    q = 2
    
    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        
        q += 1

Note that it returns a generator.

Reminiscent

This sieve is very terse. Where did it come from? – Scissure

That's a really excellent implementation of the Sieve. I've never seen it applied to indefinite ranges before, but it's obvious in retrospect. – Gerda

The dictionary operation is time-consuming, if you have enough memory, you had better save all the numbers in the memory instead of use a dictionary to add and remove elements dynamically. – Suave

@xiao I thought "in" operation was on average constant in time and at worst linear – Arrowroot

@yatisagade, hey, the dictionary implementation in python is based on dynamical set which is not laverage constant. It should be log(n). – Suave

To see this work try it out at people.csail.mit.edu/pgbovine/python/tutor.html#mode=edit – Haiku

See this thread code.activestate.com/recipes/117119-sieve-of-eratosthenes if you want to see where this code came from, and some faster refinements (4x in my tests) – Lahey

the addition of the values into the dict should really be postponed until their squares are seen in the input, as in https://mcmap.net/q/57414/-how-to-implement-an-efficient-infinite-generator-of-prime-numbers-in-python . This brings memory consumption drastically down and improves orders of growth. cf. test entry and related discussion. – Depositor

so wait how does one use this? – Fictile

@FerdinandoRandisi: it returns a generator – Reminiscent

This dynamic sieve is very cool. For calibration, making it able to run an infinite generator like this makes it about 3 times slower than a regular static sieve, which pre-populates the sieve up to sqrt(max_prime). – Osmose

And the 'postponed' version Will Ness links to takes about 0.8 the time of a simple static sieve. – Osmose

Can someone please give an example of how to use this? Repeatedly saying "It returns a generator" may not be enough to some people new to the language who don't know how to use a generator. Since this method doesn't take any arguments. I'm not able to get any output from this. – Acropetal

how to use: for prime in gen_primes(): – Genitalia

@FerdinandoRandisi one simple way to use this is print([p for i, p in zip(range(30), gen_primes())]) Another option is list(itertools.islice(gen_primes, n)). See also https://mcmap.net/q/80379/-how-to-take-the-first-n-items-from-a-generator-or-list-duplicate – Deactivate

Answer 2

re is powerful:

import re


def isprime(n):
    return re.compile(r'^1?$|^(11+)\1+$').match('1' * n) is None

print [x for x in range(100) if isprime(x)]

###########Output#############
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Fielder

Very clever! Explanation for those interested. – Haire

Very inefficient though. – Decasyllabic

Answer 3

def is_prime(num):
    """Returns True if the number is prime
    else False."""
    if num == 0 or num == 1:
        return False
    for x in range(2, num):
        if num % x == 0:
            return False
    else:
        return True

>> filter(is_prime, range(1, 20))
  [2, 3, 5, 7, 11, 13, 17, 19]

We will get all the prime numbers upto 20 in a list. I could have used Sieve of Eratosthenes but you said you want something very simple. ;)

Cornucopia

1 isn't a prime number. 2 and 3 are prime numbers and are missing. So this already doesn't work for the first three numbers. – Tuppence

If you go all the way up to the number it will mod to 0 and return false. – Percentage

The else is unnecessary. The function will return True if it is a prime without it and it may confuse beginners. – Darien

If you changed for x in range(2, num) into for x in range(2, math.trunc(math.sqrt(num)) + 1), then you get the same results, but faster. – Osmose

Answer 4

def primes(n): # simple sieve of multiples 
   odds = range(3, n+1, 2)
   sieve = set(sum([list(range(q*q, n+1, q+q)) for q in odds], []))
   return [2] + [p for p in odds if p not in sieve]

>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

To test if a number is prime:

>>> 541 in primes(541)
True
>>> 543 in primes(543)
False

Unwitting

this is not the Sieve of Eratosthenes though, because it finds composites by enumerating the multiples of odds, whereas SoE enumerates the multiples of primes. – Depositor

so, almost the sieve of Eratosthenes. still much better than trial division... – Depositor

Answer 5

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

Variometer

it is quite simple, but not efficient. on a typical pc, it takes several seconds to work in range(10000) – Fefeal

Answer 6

SymPy is a Python library for symbolic mathematics. It provides several functions to generate prime numbers.

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. 

Here are some examples.

>>> import sympy
>>> 
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Benoite

Answer 7

Here's a simple (Python 2.6.2) solution... which is in-line with the OP's original request (now six-months old); and should be a perfectly acceptable solution in any "programming 101" course... Hence this post.

import math

def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0: 
            return False;
    return n>1;

print 2
for n in range(3, 50):
    if isPrime(n):
        print n

This simple "brute force" method is "fast enough" for numbers upto about about 16,000 on modern PC's (took about 8 seconds on my 2GHz box).

Obviously, this could be done much more efficiently, by not recalculating the primeness of every even number, or every multiple of 3, 5, 7, etc for every single number... See the Sieve of Eratosthenes (see eliben's implementation above), or even the Sieve of Atkin if you're feeling particularly brave and/or crazy.

Caveat Emptor: I'm a python noob. Please don't take anything I say as gospel.

Arriaga

Answer 8

Here is a numpy version of Sieve of Eratosthenes having both okay complexity (lower than sorting an array of length n) and vectorization.

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.where(is_prime)[0]

Timings:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' time =', round(time.time()-timer,6))

>> n = 10^ 2  time = 5.6e-05
>> n = 10^ 3  time = 6.4e-05
>> n = 10^ 4  time = 0.000114
>> n = 10^ 5  time = 0.000593
>> n = 10^ 6  time = 0.00467
>> n = 10^ 7  time = 0.177758
>> n = 10^ 8  time = 1.701312
>> n = 10^ 9  time = 19.322478

Keefer

en.wikipedia.org/wiki/… FTW! – Depositor

BTW - look at the difference between n^6 and n^7. This is due to cash misses, so on a million entries it can hold the array in cash but it can't do it for 10 million. en.wikipedia.org/wiki/CPU_cache – Sunil

nice. I was dismissing it on account of the first measurement being "too small" but you actually provided an actual explanation! Empirical orders of growth is a valuable analysis tool, I can't recommend it enough. (I even posted a Q and an A about it, something about "painter puzzle", but it's got only 100 views so far...). maybe if it were more "in vogue", the pandemic response wouldn't be so slow at first, too. – Depositor

Answer 9

Another simple example, with a simple optimization of only considering odd numbers. Everything done with lazy streams (python generators).

Usage: primes = list(create_prime_iterator(1, 30))

import math
import itertools

def create_prime_iterator(rfrom, rto):
    """Create iterator of prime numbers in range [rfrom, rto]"""
    prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a "weird" case of even prime
    odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that  we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
    odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
    prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
    return itertools.chain(prefix, prime_generator)

def has_odd_divisor(num):
    """Test whether number is evenly divisable by odd divisor."""
    maxDivisor = int(math.sqrt(num))
    for divisor in xrange(3, maxDivisor + 1, 2):
        if num % divisor == 0:
            return True
    return False

def make_odd(number):
    """Make number odd by adding one to it if it was even, otherwise return it unchanged"""
    return number | 1

Hinson

Answer 10

Just studied the topic, look for the examples in the thread and try to make my version:

from collections import defaultdict
# from pprint import pprint

import re


def gen_primes(limit=None):
    """Sieve of Eratosthenes"""
    not_prime = defaultdict(list)
    num = 2
    while limit is None or num <= limit:
        if num in not_prime:
            for prime in not_prime[num]:
                not_prime[prime + num].append(prime)
            del not_prime[num]
        else:  # Prime number
            yield num
            not_prime[num * num] = [num]
        # It's amazing to debug it this way:
        # pprint([num, dict(not_prime)], width=1)
        # input()
        num += 1


def is_prime(num):
    """Check if number is prime based on Sieve of Eratosthenes"""
    return num > 1 and list(gen_primes(limit=num)).pop() == num


def oneliner_is_prime(num):
    """Simple check if number is prime"""
    return num > 1 and not any([num % x == 0 for x in range(2, num)])


def regex_is_prime(num):
    return re.compile(r'^1?$|^(11+)\1+$').match('1' * num) is None


def simple_is_prime(num):
    """Simple check if number is prime
    More efficient than oneliner_is_prime as it breaks the loop
    """
    for x in range(2, num):
        if num % x == 0:
            return False
    return num > 1


def simple_gen_primes(limit=None):
    """Prime number generator based on simple gen"""
    num = 2
    while limit is None or num <= limit:
        if simple_is_prime(num):
            yield num
        num += 1


if __name__ == "__main__":
    less1000primes = list(gen_primes(limit=1000))
    assert less1000primes == list(simple_gen_primes(limit=1000))
    for num in range(1000):
        assert (
            (num in less1000primes)
            == is_prime(num)
            == oneliner_is_prime(num)
            == regex_is_prime(num)
            == simple_is_prime(num)
        )
    print("Primes less than 1000:")
    print(less1000primes)

    from timeit import timeit

    print("\nTimeit:")
    print(
        "gen_primes:",
        timeit(
            "list(gen_primes(limit=1000))",
            setup="from __main__ import gen_primes",
            number=1000,
        ),
    )
    print(
        "simple_gen_primes:",
        timeit(
            "list(simple_gen_primes(limit=1000))",
            setup="from __main__ import simple_gen_primes",
            number=1000,
        ),
    )
    print(
        "is_prime:",
        timeit(
            "[is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import is_prime",
            number=100,
        ),
    )
    print(
        "oneliner_is_prime:",
        timeit(
            "[oneliner_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import oneliner_is_prime",
            number=100,
        ),
    )
    print(
        "regex_is_prime:",
        timeit(
            "[regex_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import regex_is_prime",
            number=100,
        ),
    )
    print(
        "simple_is_prime:",
        timeit(
            "[simple_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import simple_is_prime",
            number=100,
        ),
    )

The result of running this code show interesting results:

$ python prime_time.py
Primes less than 1000:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Timeit:
gen_primes: 0.6738066330144648
simple_gen_primes: 4.738092333020177
is_prime: 31.83770858097705
oneliner_is_prime: 3.3708438930043485
regex_is_prime: 8.692703998007346
simple_is_prime: 0.4686249239894096

So I can see that we have right answers for different questions here; for a prime number generator gen_primes looks like the right answer; but for a prime number check, the simple_is_prime function is better suited.

This works, but I am always open to better ways to make is_prime function.

Janaye

I have a fastish prime generator ( not as fast as probabilistic isprimes ) but mine is non probabilistic and is quick for that. 0.011779069900512695 to generate those primes. Located here at: github.com/oppressionslayer/primalitytest and using a for loop with the lars_next_prime function – Tectonics

Answer 11

To my opinion it is always best to take the functional approach,

So I create a function first to find out if the number is prime or not then use it in loop or other place as necessary.

def isprime(n):
      for x in range(2,n):
        if n%x == 0:
            return False
    return True

Then run a simple list comprehension or generator expression to get your list of prime,

[x for x in range(1,100) if isprime(x)]

Widen

Answer 12

This is my implementation. Im sure there is a more efficient way, but seems to work. Basic flag use.

def genPrime():
    num = 1
    prime = False
    while True:
        # Loop through all numbers up to num
        for i in range(2, num+1):
            # Check if num has remainder after the modulo of any previous numbers
            if num % i == 0:
                prime = False
                # Num is only prime if no remainder and i is num
                if i == num:
                    prime = True
                break

        if prime:
            yield num
            num += 1
        else:
            num += 1

prime = genPrime()
for _ in range(100):
    print(next(prime))

Deploy

Answer 13

python 3 (generate prime number)

from math import sqrt

i = 2
while True:
    for x in range(2, int(sqrt(i) + 1)):
        if i%x==0:
            break
    else:
        print(i)
    i += 1

Betz

Answer 14

This seems homework-y, so I'll give a hint rather than a detailed explanation. Correct me if I've assumed wrong.

You're doing fine as far as bailing out when you see an even divisor.

But you're printing 'count' as soon as you see even one number that doesn't divide into it. 2, for instance, does not divide evenly into 9. But that doesn't make 9 a prime. You might want to keep going until you're sure no number in the range matches.

(as others have replied, a Sieve is a much more efficient way to go... just trying to help you understand why this specific code isn't doing what you want)

Brann

Answer 15

You need to make sure that all possible divisors don't evenly divide the number you're checking. In this case you'll print the number you're checking any time just one of the possible divisors doesn't evenly divide the number.

Also you don't want to use a continue statement because a continue will just cause it to check the next possible divisor when you've already found out that the number is not a prime.

Weig

Answer 16

Here is what I have:

def is_prime(num):
    if num < 2:         return False
    elif num < 4:       return True
    elif not num % 2:   return False
    elif num < 9:       return True
    elif not num % 3:   return False
    else:
        for n in range(5, int(math.sqrt(num) + 1), 6):
            if not num % n:
                return False
            elif not num % (n + 2):
                return False

    return True

It's pretty fast for large numbers, as it only checks against already prime numbers for divisors of a number.

Now if you want to generate a list of primes, you can do:

# primes up to 'max'
def primes_max(max):
    yield 2
    for n in range(3, max, 2):
        if is_prime(n):
            yield n

# the first 'count' primes
def primes_count(count):
    counter = 0
    num = 3

    yield 2

    while counter < count:
        if is_prime(num):
            yield num
            counter += 1
        num += 2

using generators here might be desired for efficiency.

And just for reference, instead of saying:

one = 1
while one == 1:
    # do stuff

you can simply say:

while 1:
    #do stuff

Bosom

Answer 17

You can create a list of primes using list comprehensions in a fairly elegant manner. Taken from here:

>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Exequatur

Answer 18

How about this if you want to compute the prime directly:

def oprime(n):
counter = 0
b = 1
if n == 1:
    print 2
while counter < n-1:
    b = b + 2
    for a in range(2,b):
        if b % a == 0:
            break
    else:
        counter = counter + 1
        if counter == n-1:
            print b

Decapolis

Answer 19

Similar to user107745, but using 'all' instead of double negation (a little bit more readable, but I think same performance):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

Basically it iterates over the x in range of (2, 100) and picking only those that do not have mod == 0 for all t in range(2,x)

Another way is probably just populating the prime numbers as we go:

primes = set()
def isPrime(x):
  if x in primes:
    return x
  for i in primes:
    if not x % i:
      return None
  else:
    primes.add(x)
    return x

filter(isPrime, range(2,10000))

Pyoid

Answer 20

import time

maxnum=input("You want the prime number of 1 through....")

n=2
prime=[]
start=time.time()

while n<=maxnum:

    d=2.0
    pr=True
    cntr=0

    while d<n**.5:

        if n%d==0:
            pr=False
        else:
            break
        d=d+1

    if cntr==0:

        prime.append(n)
        #print n

    n=n+1

print "Total time:",time.time()-start

Grenadines

Answer 21

If you wanted to find all the primes in a range you could do this:

def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
    return False
for x in range(2, num):
    if num % x == 0:
        return False
else:
    return True
num = 0
itr = 0
tot = ''
while itr <= 100:
    itr = itr + 1
    num = num + 1
    if is_prime(num) == True:
        print(num)
        tot = tot + ' ' + str(num)
print(tot)

Just add while its <= and your number for the range.
OUTPUT:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

Saving

Answer 22

Using generator:

def primes(num):
    if 2 <= num:
        yield 2
    for i in range(3, num + 1, 2):
        if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
            yield i

Usage:

for i in primes(10):
    print(i)

2, 3, 5, 7

Paphlagonia

Answer 23

You could use a function to check if its prime while it's generating but this is slow, so you could use the thread module which allows you to generate primes faster:

import threading

def is_prime(num):
    if num < 2:
        return False
    return all(num % i != 0 for i in range(2, int(num ** 0.5) + 1))

def find_primes(start, end, result):
    primes = [num for num in range(start, end) if is_prime(num)]
    result.extend(primes)

def find_primes_parallel(start, end, num_threads):
    result = []
    threads = []
    segment_size = (end - start) // num_threads

    for i in range(num_threads):
        seg_start = start + i * segment_size
        seg_end = seg_start + segment_size

        if i == num_threads - 1:
            seg_end = end

        thread = threading.Thread(target=find_primes, args=(seg_start, seg_end, result))
        thread.start()
        threads.append(thread)

    for thread in threads:
        thread.join()

    return result

# Example usage
start_num = 1
end_num = 100000
num_threads = 4

primes = find_primes_parallel(start_num, end_num, num_threads)
print(primes)

Cox

Answer 24

• The continue statement looks wrong.

• You want to start at 2 because 2 is the first prime number.

• You can write "while True:" to get an infinite loop.

Atwood

Answer 25

def check_prime(x):
    if (x < 2): 
       return 0
    elif (x == 2): 
       return 1
    t = range(x)
    for i in t[2:]:
       if (x % i == 0):
            return 0
    return 1

Expense

Answer 26

def genPrimes():
    primes = []   # primes generated so far
    last = 1      # last number tried
    while True:
        last += 1
        for p in primes:
            if last % p == 0:
                break
        else:
            primes.append(last)
            yield last

Thicket

do we really need to test divide 101 by 97, to find out whether 101 is prime? – Depositor

Answer 27

For me, the below solution looks simple and easy to follow.

import math

def is_prime(num):

    if num < 2:
        return False

    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            return False

return True

Pokeweed

is_prime(121) == True, but 121 is not prime. – Pulley

@Adam: True, thanks for spotting it. I can't think of any better solution than the ones already proposed by other people in this thread. So I will re-write my solution to match one of those. If I find any new techniques, I will re-visit my solution. – Pokeweed

Answer 28

This is the fastest way to find primes up to n that I have seen. Up to 100m in 1.2 seconds. It uses pure python without dependencies

def primes(lim):
  if lim<7:
    if lim<2: return []
    if lim<3: return [2]
    if lim<5: return [2, 3]
    return [2, 3, 5]
  n = (lim-1)//30
  m = n+1
  BA = bytearray
  prime1 = BA([1])*m
  prime7 = BA([1])*m
  prime11 = BA([1])*m
  prime13 = BA([1])*m
  prime17 = BA([1])*m
  prime19 = BA([1])*m
  prime23 = BA([1])*m
  prime29 = BA([1])*m
  prime1[0] = 0
  i = 0
  try:
    while 1:
      if prime1[i]:
        p = 30*i+1
        l = i*(p+1)
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*6
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*4
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*2
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*4
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*2
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*4
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*6
        prime29[l::p] = BA(1+(n-l)//p)
      if prime7[i]:
        p = 30*i+7
        l = i*(p+7)+1
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*4+1
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*4
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*4+1
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*6+1
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime7[l::p] = BA(1+(n-l)//p)
      if prime11[i]:
        p = 30*i+11
        l = i*(p+11)+4
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*2
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*2
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*6+2
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*6+2
        prime17[l::p] = BA(1+(n-l)//p)
      if prime13[i]:
        p = 30*i+13
        l = i*(p+13)+5
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*4+1
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*6+3
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*6+3
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*4+1
        prime23[l::p] = BA(1+(n-l)//p)
      if prime17[i]:
        p = 30*i+17
        l = i*(p+17)+9
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*4+3
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*6+3
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*6+3
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*4+3
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime11[l::p] = BA(1+(n-l)//p)
      if prime19[i]:
        p = 30*i+19
        l = i*(p+19)+12
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*6+4
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*6+4
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*2+2
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*4+2
        prime23[l::p] = BA(1+(n-l)//p)
      if prime23[i]:
        p = 30*i+23
        l = i*(p+23)+17
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*6+5
        prime7[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*6+5
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*4+3
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*4+4
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime17[l::p] = BA(1+(n-l)//p)
      if prime29[i]:
        p = 30*i+29
        l = i*(p+29)+28
        prime1[l::p] = BA(1+(n-l)//p)
        l += i*2+1
        prime29[l::p] = BA(1+(n-l)//p)
        l += i*6+6
        prime23[l::p] = BA(1+(n-l)//p)
        l += i*4+4
        prime19[l::p] = BA(1+(n-l)//p)
        l += i*2+2
        prime17[l::p] = BA(1+(n-l)//p)
        l += i*4+4
        prime13[l::p] = BA(1+(n-l)//p)
        l += i*2+2
        prime11[l::p] = BA(1+(n-l)//p)
        l += i*4+4
        prime7[l::p] = BA(1+(n-l)//p)
      i+=1
  except:
    pass
  RES = [2, 3, 5]
  A = RES.append
  ti=0
  try:
    for i in range(n):
      if prime1[i]:
        A(ti+1)
      if prime7[i]:
        A(ti+7)
      if prime11[i]:
        A(ti+11)
      if prime13[i]:
        A(ti+13)
      if prime17[i]:
        A(ti+17)
      if prime19[i]:
        A(ti+19)
      if prime23[i]:
        A(ti+23)
      if prime29[i]:
        A(ti+29)
      ti+=30
  except:
    pass
  if prime1[n] and (30*n+1)<=lim:
    A(30*n+1)
  if prime7[n] and (30*n+7)<=lim:
    A(30*n+7)
  if prime11[n] and (30*n+11)<=lim:
    A(30*n+11)
  if prime13[n] and (30*n+13)<=lim:
    A(30*n+13)
  if prime17[n] and (30*n+17)<=lim:
    A(30*n+17)
  if prime19[n] and (30*n+19)<=lim:
    A(30*n+19)
  if prime23[n] and (30*n+23)<=lim:
    A(30*n+23)
  if prime29[n] and (30*n+29)<=lim:
    A(30*n+29)
  return RES

from time import time
n = time()
print (primes(100000000)[-1])
print (time() - n)

Compact

certified chatgpt moment – Flaccid

chatgpt didn't exist then – Compact