99 lines
2.8 KiB
Python
99 lines
2.8 KiB
Python
# 2.Consider a positive number n. Determine all its decompositions as sums of prime numbers.
|
|
import math
|
|
|
|
def is_prime(n:int)->bool:
|
|
"""
|
|
params: n - Integer
|
|
return: Boolean
|
|
|
|
Returns True if n is prime, False otherwise.
|
|
"""
|
|
if n<2:
|
|
return False
|
|
for i in range(2,math.floor(n**(1/2))+1):
|
|
if n%i==0:
|
|
return False
|
|
return True
|
|
|
|
def primes_smaller_or_equal_to_n(n:int)->list:
|
|
"""
|
|
params: n - Integer
|
|
return: List
|
|
|
|
Returns the list of all prime numbers smaller or equal to n.
|
|
"""
|
|
primes=[]
|
|
for i in range(2,n+1):
|
|
if is_prime(i):
|
|
primes.append(i)
|
|
return primes
|
|
|
|
def iterative(n):
|
|
"""
|
|
params: n - Positive Integer
|
|
return: List
|
|
|
|
Returns every decompositions of the number n in a list of lists, each set containing the primes.
|
|
If no such decomposition exists, returns an empty list.
|
|
The computation is done in an iterative way.
|
|
"""
|
|
list_of_primes=primes_smaller_or_equal_to_n(n)
|
|
count_stack=[]
|
|
count=len(list_of_primes)
|
|
solution=[]
|
|
current_solution=[]
|
|
while count:
|
|
number=list_of_primes[count-1]
|
|
count-=1
|
|
if sum(current_solution)+number < n:
|
|
current_solution.append(number)
|
|
count_stack.append(count)
|
|
count=len(list_of_primes)
|
|
elif sum(current_solution)+number == n:
|
|
current_solution.append(number)
|
|
c=sorted(current_solution)
|
|
if c not in solution:
|
|
solution.append(c)
|
|
current_solution.pop()
|
|
while count_stack and count==0:
|
|
current_solution.pop()
|
|
count=count_stack.pop()
|
|
return solution
|
|
|
|
def recursive(n,current_solution,list_of_primes):
|
|
"""
|
|
params: n - Positive Integer
|
|
return: List
|
|
|
|
Returns every decompositions of the number n in a list of lists, each set containing the primes.
|
|
If no such decomposition exists, returns an empty list.
|
|
The computation is done in a recursive way
|
|
"""
|
|
solution=[]
|
|
if sum(current_solution)<n:
|
|
for i in list_of_primes:
|
|
c=current_solution+[i]
|
|
s=recursive(n,c,list_of_primes)
|
|
if s!=[]:
|
|
if isinstance(s[0],list):
|
|
for e in s:
|
|
if e not in solution:
|
|
solution.append(e)
|
|
else:
|
|
if s not in solution:
|
|
solution.append(s)
|
|
return solution
|
|
elif sum(current_solution)==n:
|
|
return sorted(current_solution)
|
|
else:
|
|
return []
|
|
|
|
def recursive_imp(n):
|
|
return recursive(n,[],list_of_primes=primes_smaller_or_equal_to_n(n))
|
|
|
|
if __name__ == "__main__":
|
|
n=int(input("Please enter a number: "))
|
|
print("Recursive: ")
|
|
print(recursive_imp(n))
|
|
print("Iterative:")
|
|
print(iterative(n)) |