Skip to content

Instantly share code, notes, and snippets.

@mydreambei-ai
Last active June 30, 2017 07:38
Show Gist options
  • Save mydreambei-ai/4c29ab36ec75ef1cde8ebb7451b7ef1e to your computer and use it in GitHub Desktop.
Save mydreambei-ai/4c29ab36ec75ef1cde8ebb7451b7ef1e to your computer and use it in GitHub Desktop.
check less n primes (good, better methods)
import math
def tri_prime(n):
primes = [2]
def is_prime(number):
if number % 2 == 0: return False
for i in range(3, math.floor(number / 2) + 1):
if number % i == 0:
return False
return True
for i in range(3, n + 1):
if is_prime(i):
primes.append(i)
return primes
def good_prime(n):
primes = [2]
def is_prime(number):
if number % 2 == 0 and n > 2:
return False
return all(number % i for i in range(3, int(math.sqrt(number)) + 1, 2))
for i in range(3, n + 1):
if is_prime(i):
primes.append(i)
return primes
def better_prime(n):
primes = [2]
def is_prime(number):
if number % 2 == 0: return False
sqrt_n = int(math.sqrt(number))
for p in primes:
if p > sqrt_n: return True
if number % p == 0: return False
if sqrt_n <= primes[-1]:
return True
elif sqrt_n > primes[-1]:
# almost do not
return all(number % j for j in range(primes[-1], sqrt_n + 1, 2))
for i in range(3, n + 1):
if is_prime(i):
primes.append(i)
return primes
def odd_prime(n):
primes = [2, 3]
def is_prime(number):
if number % 2 == 0 or number % 3 == 0: return False
x = int((number - 3) / 2)
y = 1
for i in range(x, 1, -3):
if i >= y:
if y != 1 and i % y == 0:
return False
else:
break
y += 2
return True
for i in range(5, n + 1):
if is_prime(i):
primes.append(i)
return primes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment