blob: da2216e3ea56fd49dc939b141af5871838e1020f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#!/usr/bin/python3
# Challenge 076
#
# TASK #1 > Prime Sum
# Submitted by: Mohammad S Anwar
# Reviewed by: Ryan Thompson
# You are given a number $N. Write a script to find the minimum number of
# prime numbers required, whose summation gives you $N.
#
# For the sake of this task, please assume 1 is not a prime number.
#
# Example:
# Input:
# $N = 9
#
# Ouput:
# 2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
# 2 + 7 = 9.
import sys
from primePy import primes
from itertools import combinations
def next_prime(n):
if n <= 1:
return 2
else:
n += 1
while not primes.check(n):
n += 1
return n
# check all combinations for the shortest that adds up to N
def find_set(n):
# get all primes up to N, 1 not included;
# append primes 2 and 3 to be able to solve special cases 4 and 6
terms = primes.upto(n)
terms.extend([2, 3])
solution = []
for k in range(1, len(terms)+1):
for combin in combinations(terms, k):
if sum(combin)==n:
if len(solution)==0 or len(solution)>len(combin):
solution = sorted(list(combin))
if len(solution)==1:
return solution # special case - is prime
return solution
n = int(sys.argv[1])
solution = find_set(n)
print(" + ".join([str(x) for x in solution])+" = "+str(n))
|
