CODEWITHSUNDEEP
pythonrecursion
starshine
starshine

Reputation: 55

Sum of Prime using Recursion in Python

The problem given is to determine whether two numbers m and n are prime or not, and if they are, give the sum of all prime numbers from m to n. I have already made a code for the first part:

def isPrime(n, i):
    if n <= i:
        return True if (n == 2) else False
    if n % i == 0:
        return False
    if i * i > n:
        return True
    return isPrime(n, i + 1)

However, I don't know how to do the second part of the code. A clue that our professor gave to us was to call the first function in the second part of the code, like this:

def sumOfPrime(m, n):
    **enter code here**
        isPrime(m, 2)
        isPrime(n, 2)

I've no idea how to know all the prime numbers from m to n. Also, we are only allowed to use recursion for this problem.

Upvotes: 1

Views: 927

Answers (2)

Christian Sloper
Christian Sloper

Reputation: 7510

Here is a fully recursive version:

def sumOfPrime(m,n):
    if isPrime(n,2) and isPrime(m,2):
        return sumOfPrimes(m,n)

def sumOfPrimes(m, n):
    if m > n:
        return 0
    return (m if isPrime(m,2) else 0) + sumOfPrimes(m+1,n)

If only one function, maybe better with a nestet function:

def sumOfPrime(m,n):
    def helper(m,n):
        if m > n:
            return 0
        return (m if isPrime(m,2) else 0) + sumOfPrimes(m+1,n)

    if isPrime(n,2) and isPrime(m,2):
        return helper(m,n)


assert sumOfPrime(2,5) == 2 +3 + 5

Upvotes: 1

Ngoc N. Tran
Ngoc N. Tran

Reputation: 1068

I assume your professor wants you to just test all numbers between m and n for primality, then add those that pass together.

def sumOfPrime(m, n):
    if isPrime(m, 2) and isPrime(n, 2):
        return sum(i for i in range(m, n + 1) if isPrime(i, 2))

Upvotes: 1

Related Questions