EDIT
I would like to point out that there is a tiny wrong part here. You can not continue the blacklist like i did. you need to wait before you remove (only remove whats a part of the base value)
2 * 3 = 6 (no issues)
2 * 3 * 5 = 30 (remove 25 because its 5x5, and its in the base)
2 * 3 * 5 * 7 = 210 (remove 7x7, 7x11... because 7 is in the base. we want to avoid making primes out anything including 7 in base 210, but we still want to keep 11x11, 11x13...)
THIS also means, when you want to produce the final list with all primes to show off. you need to remove EVERY value that is a primeXprime. you know where to start, bacause its the next prime you would add to the base list
EDIT
(This not a question or solution to a prior question. just a project.)
Finds primes based on the lines appearing when sorting the last digit
In Base 10 [2*5] they will appear in [1, 3, 7, 9] (4/10 = 40% of all numbers in base 10)
In Base 6 [2*3] they will appear in [1, 5] (2/6 = 33.34% of all numbers in base 6)
In Base 30 [2*3*5] they will appear in [1, 7, 11, 13, 17, 19, 23, 29] (8/30 = 26.67% of all numbers in base 30)
Why do they appear like this? lets take Base 10, and Base 6 as an example.
--Base 10
0 = This is the base value, since 10 = 2*5, it will not be a prime Line
1 = Prime, in [2, 5] : false => line
2 = Prime, in [2, 5] : true
3 = Prime, in [2, 5] : false => line
4 = 2*2 = (2 || 2) in [2, 5] : true
5 = Prime, in [2, 5] : true
6 = 3*2 = (3 || 2) in [2, 5] : true
7 = Prime, in [2, 5] : false => line
8 = 2*2*2 = (2 || 2 || 2) in [2, 5] : true
9 = 3*3 = (3 || 3) in [2, 5] : false => line
--Base 6
0 = This is the base value, since 6 = 2*3, it will not be a prime Line
1 = Prime, in [2, 3] : false => line
2 = Prime, in [2, 3] : true
3 = Prime, in [2, 3] : true
4 = 2*2 (2 || 2) in [2, 3] : true
5 = Prime, in [2, 3] : false => line
pattern exmple:
base 30 [2, 3, 5]
lines [1, 7, 11, 13... 29]
lines are missing all primes inside base.
But there is still one issue. The lines are just potential primes.
If you write base 6 and base 30 down and add values in just the lines you will see primes, and another pattern of non primes.
these nonprimes have composites made only from primes that are not in the base array.
Example: base 6 [2, 3] - 5x5=25, 5x7=30... 7x7=49... and so on. This makes it easier to make a blacklist function to remove them.
Since the amount of possible blacklisted numbers increase the longer we stay at the current base, and the efficiancy increases the larger the base value (if [2, 3, nextPrime, nextPrime, nextPrime...]) we want so begin to use the next base as soon as possible. There is an easy way to find when to stop looking for primes in the current base: [BasePrimes, NextPrime] will yeald the endpoint, because we have enought primes to start looking for primes in the next base.
from numpy import prod #Finds primes based on the lines appearing when sorting the last digit #In Base 10 [2*5] they will appear in [1, 3, 7, 9] (4/10 = 40% of all numbers in base 10) #In Base 6 [2*3] they will appear in [1, 5] (2/6 = 33.34% of all numbers in base 6) #In Base 30 [2*3*5] they will appear in [1, 7, 11, 13, 17, 19, 23, 29] (8/30 = 26.67% of all numbers in base 30) #... def prime(x): primes = { 1: True, 2: True, 3: True, 5: True } loop, nextBase = primeHelper(primes, x) return dictPrimeList(primes, loop, nextBase) #Removes non prime integers through a pattern, Example: (Note: might not fully work as intended yet) #baseValue = [2, 3, 5] with currentBase = 30 #nextValue = [2, 3, 5, 7] with nextBase = 210 # # ---DEL--- # 41(7x7) 77(7x11) 91(7x13) 119(7x17) 133(7x19) 161(7x23) 203(7x29) ---> 217(7x31) > nextBase(210) : break # 121(11x11) 143(11x13) 187(11x17) 209(11x19 ---> 253(11x23) > nextBase(210) : break # 169(13x13) ---> 221(13x17) > nextBase(210) : break # we can already tell by 13x17 that 17x17 will go over : break def blackPrimeList(primes, baseValue, primesList, nextBase, main = True): for i in range(baseValue, len(primesList)): testing = primesList[baseValue]*primesList[i] if testing > nextBase: break try: del primes[testing] except: pass if main: blackPrimeList(primes, i+1, primesList, nextBase, False) #Creates a list from Object, by counting even(2) numbers up and checking if they are primes (Because all primes are odd other than 2) def dictPrimeList(primes, loop, nextBase): primesList = [1, 2, 3, 5] primesLen = nextBase for x in range(5 ,primesLen, 2): if not x == 5: try: if primes[x]: primesList.append(x) except: pass return primesList #Main function Helper def primeHelper(primes, loops): loop = 0 primesList = dictPrimeList(primes, loop, 30) baseValue = [primesList[1], primesList[2]] while True: currentBase = prod(baseValue) nextBase = currentBase * primesList[len(baseValue)+1] blacklist = [] #Last prime appended during prior run for x in range(len(primes)-1, -1, -1): if primesList[x] < currentBase: lastPosition = x break #Make potential primes for base in range(currentBase, nextBase, currentBase): for prime in primesList[:lastPosition+1]: if prime in baseValue: continue primes[base+prime] = True #Correct potential primes primesList = dictPrimeList(primes, loop, nextBase) blackPrimeList(primes, len(baseValue)+1, primesList, nextBase) primesList = dictPrimeList(primes, loop, nextBase) #End section loop += 1 if loop >= loops: return loop, nextBase baseValue.append(primesList[len(baseValue)+1])
from math import sqrt- from numpy import prod
- #Finds primes based on the lines appearing when sorting the last digit
- #In Base 10 [2*5] they will appear in [1, 3, 7, 9] (4/10 = 40% of all numbers in base 10)
- #In Base 6 [2*3] they will appear in [1, 5] (2/6 = 33.34% of all numbers in base 6)
- #In Base 30 [2*3*5] they will appear in [1, 7, 11, 13, 17, 19, 23, 29] (8/30 = 26.67% of all numbers in base 30)
- #...
- def prime(x):
end = min(int(sqrt(x) + 1), x)return all(x % i != 0 for i in range(2, end))- primes = {
- 1: True,
- 2: True,
- 3: True,
- 5: True
- }
- loop, nextBase = primeHelper(primes, x)
- return dictPrimeList(primes, loop, nextBase)
- #Removes non prime integers through a pattern, Example: (Note: might not fully work as intended yet)
- #baseValue = [2, 3, 5] with currentBase = 30
- #nextValue = [2, 3, 5, 7] with nextBase = 210
- #
- # ---DEL---
- # 41(7x7) 77(7x11) 91(7x13) 119(7x17) 133(7x19) 161(7x23) 203(7x29) ---> 217(7x31) > nextBase(210) : break
- # 121(11x11) 143(11x13) 187(11x17) 209(11x19 ---> 253(11x23) > nextBase(210) : break
- # 169(13x13) ---> 221(13x17) > nextBase(210) : break
- # we can already tell by 13x17 that 17x17 will go over : break
- def blackPrimeList(primes, baseValue, primesList, nextBase, main = True):
- for i in range(baseValue, len(primesList)):
- testing = primesList[baseValue]*primesList[i]
- if testing > nextBase:
- break
- try:
- del primes[testing]
- except:
- pass
- if main:
- blackPrimeList(primes, i+1, primesList, nextBase, False)
- #Creates a list from Object, by counting even(2) numbers up and checking if they are primes (Because all primes are odd other than 2)
- def dictPrimeList(primes, loop, nextBase):
- primesList = [1, 2, 3, 5]
- primesLen = nextBase
- for x in range(5 ,primesLen, 2):
- if not x == 5:
- try:
- if primes[x]:
- primesList.append(x)
- except:
- pass
- return primesList
- #Main function Helper
- def primeHelper(primes, loops):
- loop = 0
- primesList = dictPrimeList(primes, loop, 30)
- baseValue = [primesList[1], primesList[2]]
- while True:
- currentBase = prod(baseValue)
- nextBase = currentBase * primesList[len(baseValue)+1]
- blacklist = []
- #Last prime appended during prior run
- for x in range(len(primes)-1, -1, -1):
- if primesList[x] < currentBase:
- lastPosition = x
- break
- #Make potential primes
- for base in range(currentBase, nextBase, currentBase):
- for prime in primesList[:lastPosition+1]:
- if prime in baseValue:
- continue
- primes[base+prime] = True
- #Correct potential primes
- primesList = dictPrimeList(primes, loop, nextBase)
- blackPrimeList(primes, len(baseValue)+1, primesList, nextBase)
- primesList = dictPrimeList(primes, loop, nextBase)
- #End section
- loop += 1
- if loop >= loops:
- return loop, nextBase
- baseValue.append(primesList[len(baseValue)+1])
print(prime(5)) #6 will Max buffer
test.assert_equals(prime(12345),False)test.assert_equals(prime(2),True)test.assert_equals(prime(3),True)test.assert_equals(prime(4),False)test.assert_equals(prime(12),False)- print(prime(5)) #6 will Max buffer