Prime partitioning a number
Question:-
A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0 and both p and q are prime numbers.
Write a Python function primepartition(m) that takes an integer m as input and returns True if m can be partitioned as primes and False otherwise. (If m is not positive, your function should return False.)
Here are some examples of how your function should work.
>>> primepartition(7) True >>> primepartition(185) False >>> primepartition(3432) True
Solution:-
The idea behind the solution is that I'm computing all the prime numbers till the given number and appending to a list . Then I'm iterating over the list and subtracting it from the given number, if the subtracted value is prime then I'm returning True, otherwise after the loop ends returning False
def primes(n): l = [] for i in range(2,n): flag = 0 for j in range(2,i-1): if i % j == 0: flag = 1 if flag == 0: l.append(i) return l def prime_check(n): flag = 0 for i in range(2,n-1): if n % i == 0: flag = 1 if flag == 0: return True else: return False def primepartition(n): if n < 0: return False else: l = primes(n) for i in l: check = n - i if prime_check(check): return True return False
Comments
Post a Comment