#!/usr/bin/python3 # -*- coding: UTF-8 -*-# enable debugging # ###### Prime Number sieve ###### ###### Author: Jowan Worth and his dad a bit ###### 2020.10.07 first try as a command line python3 program ###### 2020.10.08 Converted to cgi-bin python3 script for apache2 webpage ###### 2020.10.10 added plot ###### import os, cgi, cgitb, sys, math, json cgitb.enable(display=1, logdir="/cgi-bin/error.log") os.environ[ 'HOME' ] = '/tmp/' def fnHelp(): import datetime x = datetime.datetime.now() stardate = x.strftime("%Y.%j") print("

### How to make it go

It makes prime numbers below 99999000000000") print("
the first entry is the smallest number in the range to look at, minimum 0") print("
then the range size, minimum 100, maximum and default 1000000") print("
and do you want to print all the primes in the range please tick") print("
") print("
I coded the prime loop and the sieve") print("
dad coded the graph and the forms, and copied my html into the program") print("
and he added cgi to my website so the program would run on it") print("
") print("
Captain's log, stardate " + stardate + "") print("") sys.exit() def fnHeader(): print("Content-Type: text/html; charset=utf-8\n") print(""" Jowan Worth's homepage

# Yew!

### Prime numbers on a Raspberry Pi

""") def fnError(text): print("

", text, "

") print("") sys.exit() def fnPlot(plotType): import matplotlib matplotlib.use('SVG') import matplotlib.pyplot as plt fig = plt.figure() with open('range') as f: bigPrimes = json.load(f) description = bigPrimes.pop() if plotType == "plot": print("
###### Graph: counts of gaps between " + description + "
") print("Take each prime in the range from the next to find the gap") print("
Each vertical bin shows how many times that gap happened in the range") print("
Longer gaps are less frequent than shorter gaps") print("
Gaps which are a multiple of 6 are more frequent than their neighbours") print("") else: print("
###### Graph: counts of gap differences between " + description + "
") print("Take each prime in the range from the next to find the gap") print("
Each vertical bin shows how the gap changes up or down from the one before") print("
Big jumps or drops are less frequent than smaller ones") print("
Jumps and drops which are a multiple of 6 are less frequent than their neighbours") print("
The bin scale zero is the biggest fall in gap length, the peak is -2, 0, +2") print("") print("") gap1 = [] gap2 = [] min1 = 999 max1 = 0 min2 = 999 max2 = 0 startRange = 0 if bigPrimes == 2: startRange = 1 for i in range(startRange,len(bigPrimes)): if i > startRange: val1 = bigPrimes[i]-bigPrimes[i-1] gap1.append(val1) if max1 < val1: max1 = val1 if min1 > val1: min1 = val1 if i > startRange + 1: val2 = (bigPrimes[i]-bigPrimes[i-1]) - (bigPrimes[i-1]-bigPrimes[i-2]) gap2.append(val2) if max2 < val2: max2 = val2 if min2 > val2: min2 = val2 for i in range(len(gap2)): gap2[i] = gap2[i] - min2 with open('gap1', 'w') as f: json.dump(gap1, f) with open('gap2', 'w') as f: json.dump(gap2, f) pot1 = [] lab1 = [] for i in range(min1,max1+1): pot1.append(0) lab1.append(i) for i in range(len(gap1)): j = gap1[i] - min1 pot1[j]+=1 with open('pot1', 'w') as f: json.dump(pot1, f) if plotType == "plot": plt.hist(gap1,bins=int((max1-min1)/2+1),log=True) # plt.stem(pot1) else: plt.hist(gap2,bins=int((max2-min2)/2+1),log=True) plt.savefig('../images/filename.svg') print(" ") print("") sys.exit() def fnEnd(): print("""
""") print("") sys.exit() # ###### Part 1 - the beginning: get the python code into cgi with html and forms # form = cgi.FieldStorage() bFrom = form.getvalue('from') bSize = form.getvalue('size') bPrint = form.getvalue('print') fnHeader() if "plot" in form: if "plotdiff" in form: fnPlot("plotdiff") else: fnPlot("plot") if "from" not in form or bFrom == "-h" or bFrom == "--help" or bFrom == "/?": fnHelp() if str.isdigit(bFrom) == False: fnError("from is not numeric") if int(bFrom) > 99999000000000: fnError("argument is too large") low = int(bFrom) size = 1000000 if "size" in form and bSize.isdigit() == True: if int(bSize) > 99 and int(bSize) < 1000000: size = int(bSize) printPrimes = False if "print" in form and bPrint: printPrimes = True #print("

All primes from %s in a range of size %s:" % (bFrom, bSize),"

") # ###### Part 2 - bring in a pre-built primes array for the sieve, creating it the slow way if this is the first run # try: with open('workfile') as f: primes = json.load(f) except IOError: print("

wait just a minute! I need to create a missing workfile...") primes =  for test in range(3, 9999999, 2): i = 0 isPrime = True while primes[i] <= math.sqrt(test): if (test % primes[i]) == 0: isPrime = False i += 1 if isPrime: primes.append(test) with open('workfile', 'w') as f: json.dump(primes, f) # ###### Part 3 - the sieve # buffer = [] high = low + size for i in range(0, size): buffer.append(True) if primes.count(low) == 0: # so long as low is not a prime! buffer = False if low < 2: # in case the range starts at 0 or 1, nothing else will eliminate 0 or 1 as a prime! buffer[1-low] = False i = 0 primesFound = 0 while primes[i]**2 < high: j = (low) // primes[i] * primes[i] if j <= low: j = j + primes[i] if j == primes[i]: j = j + primes[i] # the first use of a prime is prime, so skip to the next! while j < high: buffer[j - low] = False j = j + primes[i] i+=1 # ###### Part 4 - count and store the sieved primes to make the plots # bigPrimes = [] for i in range(low, high): if buffer[i - low]: if printPrimes: print(i, end=" ") bigPrimes.append(i) primesFound+=1 description = str(primesFound)+" primes found out of "+str(size)+" between "+str(low)+" and "+str(high) print("

",description,"

") bigPrimes.append(description) with open('range', 'w') as f: json.dump(bigPrimes, f) fnEnd()