Count prime results of polynomial

user_12214934 0
Viewed 129

Can someone help me and tell me why this doesn't work? The goal is to count the number of prime numbers that are produced by a given polynomial for inputs n in a specified range [a,b]:

    def count_primes(poly, a, b):
    primes = 0
    if b >= a:
        for n in range(a, b):
            result = poly(n)
            if result > 1:
                for i in range(2, result):
                    if (result % i) == 0:
                        break
                    else:
                        primes += 1
            else:
                break
    return primes


def poly(n):
    return n**2 + n + 41


print(count_primes(poly, 0, 39))

The result should return 40 in this case.

[2] Problem Solution Step-1. Take in the number to be checked and store it in a variable. Step-2. Initialize the count variable to 0. Step-3. Let the for loop range from 2 to half of the number (excluding 1 and the number itself). Step-4. Then find the number of divisors using the if statement and increment the count variable each time. Step-5. If the number of divisors is lesser than or equal to 0, the number is prime. Step-6. Print the final result. Step-7. Exit.

polynomials primes python
3 Answers

This is the wrong way to count primes:

        if result > 1:
            for i in range(2, result):
                if (result % i) == 0:
                    break
                else:
                    primes += 1

Should be:

        if result > 1:
            isPrime = True
            for i in range(2, result):
                if (result % i) == 0:
                    isPrime = False
                    break
            if isPrime:
                primes += 1

Also, it goes without saying. Easy optimizations for prime number detection. You only have to test for divisibility divisibility with 2 and all odd numbers between 3 and sqrt(result).

user_1044580

The problem is that the else clause in the nested loop refers to the if, when it should be activated only if the loop finished without break. Just change the identitation to:

if result > 1:
    for i in range(2, result):
        if (result % i) == 0:
            break
    else:
        primes += 1
user_119450020 
def count_primes(poly, a, b):
    primes = 0
    if b >= a:
        for n in range(a, b+1):
            result = poly(n)
            if result > 1:
                for i in range(2, result):
                    if (result % i) == 0:
                        break
                else:
                    primes += 1
            else:
                break
    return primes


def poly(n):
    return n**2 + n + 41


print(count_primes(poly, 0, 39))

Problems:

  1. you do primes += 1 too early. In your methods, you have to test until no possible division happens, then do the addition.

  2. [a, b] The endpoints are both inclusive. Then you should use b+1 at your for n in range(a, b+1), which produces 40.

user_30575870
Related