WikiSysop: Created page with "You know how I often use primes in my examples, so I decided to make a prime number generator class as an example.
It is able to generate a range of primes, somewhat similar to the way '''range()''' works.
Wanting to be smart, I decided to store the primes I have already computed in a class variable, so I do not have to compute them again at least while the program runs.
I am doing a running incremental calculation of primes, storing them as I find them, and..."

2026-01-27T08:32:51Z

Created page with "You know how I often use primes in my examples, so I decided to make a prime number generator class as an example. It is able to generate a range of primes, somewhat similar to the way '''range()''' works. Wanting to be smart, I decided to store the primes I have already computed in a class variable, so I do not have to compute them again at least while the program runs. I am doing a running incremental calculation of primes, storing them as I find them, and..."

New page

You know how I often use primes in my examples, so I decided to make a prime number generator class as an example. 
It is able to generate a range of primes, somewhat similar to the way '''range()''' works. 
Wanting to be smart, I decided to store the primes I have already computed in a class variable, so I do not have to compute them again at least while the program runs. 
I am doing a running incremental calculation of primes, storing them as I find them, and using them in my computation for the next prime. This is probably the most efficient naive implementation of finding primes. Better solutions require mathematical theories about primes - not going there. All I work with is the fact that primes are only divisible by 1 and the prime itself. Anything else in this code is deduction and inference.
This is a type of performance improvement called caching, i.e. remembering your results, so they can be reused. 
It is possible to do something similar when computing the factorial - using a dict to store the results. The key observation to see this is possible, is that if you calculated 5!, you have also calculated 4!, 3!, 2!, 1! on the way. You might as well save these results, so you do not have to compute them again.
<pre>
#!/usr/bin/env python3
# Prime number generator

class PrimeGenerator:
# Class varible, known primes in consecutive order, can be extended, but must contain these
knownprimes = [2, 3]
# Highest tested number for prime
highesttested = 3

# Instatiation
def __init__(self, number=None):
if number is not None:
# Don't catch an exception below - it does want we want.
number = int(number)
self.target = number

# Initializing iteration
def __iter__(self):
if self.target is None:
raise ValueError("No number specified")
self.pos = 0
return self

# Find next prime
def __next__(self):
# Can we use the list of known primes to find the next?
if self.pos < len(self.knownprimes):
nextprime = self.knownprimes[self.pos]
if nextprime >= self.target:
raise StopIteration
self.pos += 1
return nextprime
# No, start computing the next prime
while self.target > PrimeGenerator.highesttested+1:
PrimeGenerator.highesttested += 1
if self._isprime(PrimeGenerator.highesttested):
self.knownprimes.append(PrimeGenerator.highesttested)
self.pos += 1
return self.highesttested
raise StopIteration

# Private method for identifying a prime
def _isprime(self, number):
factor = 0
pos = 0
while factor*factor <= number:
# find next potential factor either in known primes or odd numbers above last known prime
if pos < len(self.knownprimes):
factor = self.knownprimes[pos]
pos += 1
else:
factor += 2
# test if it truly is a factor
if number % factor == 0:
return False
return True

# It is nice be able to ask if an number is a prime
def isprime(self, number=None):
if number is None:
number = self.target
if number is None:
raise ValueError("Number expected")
if number in PrimeGenerator.knownprimes:
return True
if number <= PrimeGenerator.highesttested:
return False
return self._isprime(number)

if __name__ == "__main__":
# Small testing
for i in PrimeGenerator(1000):
print(i)

print(PrimeGenerator().isprime(1000000016531)) # True
print(PrimeGenerator().isprime(1000000016521)) # False

# Big prime, don't try
# 999296950101072104250052714631
</pre>

Example code - Classes - Revision history