Skip to content

Instantly share code, notes, and snippets.

@velociraptors
velociraptors / gist:942719
Created April 26, 2011 17:37
Recursively calculates the prime factorization of any given number
def prime_factorization(inputvalue, sieve = True, primes = None):
"""
Takes an Integer argument and returns a the prime factorization as a list.
e.g. prime_factorization(45) => [3, 3, 5]
Optional arguments are 'sieve' and 'primes'; default values are 'True' and
'None' respectively. Setting sieve to 'False' commits the user to providing
a set of primes as a list.
e.g. prime_factorization(45, sieve=False, primes=[3]) => [3, 3]
"""
@velociraptors
velociraptors / what_is_this_i_don't_even.txt
Created February 10, 2011 17:03
This is production code. It has shipped with multiple versions of the software.
#if 0
SAFEARRAY psa;
VARIANT vNewData;
BindVariantToData(i, &vNewData, &psa);
#else
SAFEARRAY aSa;
VARIANT vNewData;
BindVariantToData(i, &vNewData, &aSa);
#endif
# Think of the array in this manner:
# _ i --> _
# ARRAY = |00 | In the top level list, indices are i
# | 11 | In the nested lists, indices are j
# j | 22 |
# | | 33 |
# V | 44 |
# |_ 55 _|
from time import time
def euler_sieve(n):
# source: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
# Create a candidate list within which non-primes will
# marked as None, noting that only candidates below
# sqrt(n) need be checked.
candidates = range(n+1)
fin = int(n**0.5)
LIMIT = 20001
NATURALS = range(3,LIMIT, 2)
PRIMES = [2]
current = 0
max = LIMIT
while len(NATURALS) > 0:
current = NATURALS.pop(0)
PRIMES.append(current)
i = current