WikiSysop at 10:04, 20 March 2024

2024-03-20T10:04:04Z

← Older revision		Revision as of 12:04, 20 March 2024
Line 9:		Line 9:
	# Prime number generator		# Prime number generator

	class ~~primegen~~:		class PrimeGenerator:
	# Class varible, known primes in consecutive order, can be extended, but must contain these		# Class varible, known primes in consecutive order, can be extended, but must contain these
	knownprimes = [2, 3]		knownprimes = [2, 3]
Line 39:		Line 39:
	return nextprime		return nextprime
	# No, start computing the next prime		# No, start computing the next prime
	while self.target > ~~primegen~~.highesttested+1:		while self.target > PrimeGenerator.highesttested+1:
	~~primegen~~.highesttested += 1		PrimeGenerator.highesttested += 1
	if self._isprime(~~primegen~~.highesttested):		if self._isprime(PrimeGenerator.highesttested):
	self.knownprimes.append(~~primegen~~.highesttested)		self.knownprimes.append(PrimeGenerator.highesttested)
	self.pos += 1		self.pos += 1
	return self.highesttested		return self.highesttested
Line 69:		Line 69:
	if number is None:		if number is None:
	raise ValueError("Number expected")		raise ValueError("Number expected")
	if number in ~~primegen~~.knownprimes:		if number in PrimeGenerator.knownprimes:
	return True		return True
	if number <= ~~primegen~~.highesttested:		if number <= PrimeGenerator.highesttested:
	return False		return False
	return self._isprime(number)		return self._isprime(number)

	~~# Small testing~~
	~~for i in primegen(10000):~~
	~~print(i)~~

	~~print(primegen().isprime~~(~~1000000016531)~~) ~~# True~~		if __name__ == "__main__":
	print(~~primegen(~~)~~.isprime(1000000016521)) # False~~		# Small testing
			for i in PrimeGenerator(1000):
			print(i)

	# Big prime, don't try		print(PrimeGenerator().isprime(1000000016531)) # True
	# 999296950101072104250052714631		print(PrimeGenerator().isprime(1000000016521)) # False

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

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..."

2024-03-06T14:02:11Z

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 primegen:
# 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 > primegen.highesttested+1:
primegen.highesttested += 1
if self._isprime(primegen.highesttested):
self.knownprimes.append(primegen.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 primegen.knownprimes:
return True
if number <= primegen.highesttested:
return False
return self._isprime(number)

# Small testing
for i in primegen(10000):
print(i)

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

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

Example code - Classes - Revision history

WikiSysop at 10:04, 20 March 2024