# Python Implementation
Uses [[Sieve of Eratosthenes]].
```run-python
def sieve(n):
prime = []
for i in range(n+1):
prime = prime + [1] #assume all vals prime
prime[0] = 0 #apart from 0 and 1
prime[1] = 0
#sieve process below, so prime[i] becomes 0 if i is not prime
p = 2
while 2*p <= n:
for i in range(2*p,n+1,p):
prime[i] = 0
p = p + 1
while prime[p] == 0:
p = p + 1
#create list to return
ls = []
for i in range(2,n+1):
if prime[i]:
ls = ls+[i]
return ls
def primefactorisation(n):
ls = sieve(n)
if n in ls: #deal with case that n is prime
return [n],[1] #first list is primes in the
#factorisation, second list is their multipcities
mult = [0]* len(ls) #used to store the mutiplicities of each prime (including those that don't appear)
for i in range(len(ls)):
while n % ls[i] == 0 and n != 1: #keep pulling out the lowest prime you can as a factor
mult[i] += 1 #recording how many time this was none for the ls[i]
n = n//ls[i] #take out the factor prime ls[i] while it is possible to do so
# next create primes and multiplicities lists to return
primes = []
retmult = []
for i in range(len(ls)):
if mult[i]>0:
primes += [ls[i]]
retmult += [int(mult[i])]
return primes, retmult
#test
print(primefactorisation(91))
```