Understanding the logic of this prime number generator output-CodePudding

This code is meant to output prime numbers within a given range:

def sqrt(n):
    return n**0.5

# find primes
def primes(minNum, maxNum):
    primes_sum = 0
    for i in range(minNum, maxNum):
        current_max = int(sqrt(i))
        for n in range(2, current_max   1):
            if(i%n == 0):
                break
            else:
                primes_sum  = i
                print(i)
                break
            
    print('\nSum of all primes: ', primes_sum)
        
primes(10, 20)

However, I get an incorrect output:

11, 13, 15, 17, 19

Does someone know how the 15 manages to appear? I put print statements in the first if statement block to verify that 15 is detected by the if(i%n == 0) condition, and it is, but somehow it still appears in my final output and I can't figure out why.

CodePudding user response：

I made changes to your code. Try in this way:

def sqrt(n):
    return n**0.5

# find primes
def primes(minNum, maxNum):
    primes_sum = 0
    for i in range(minNum, maxNum):
        current_max = int(sqrt(i))
        #print(current_max)
        flag = True
        for n in range(2, current_max   1):
            #print(i,n)
            if(i%n == 0):
                flag = False
        if flag:
            print(i)
            primes_sum  = i

            
    print('\nSum of all primes: ', primes_sum)
        
primes(10, 200)

In your code, you are not checking whether all the number is divisible by all the numbers. It will fail for all the odd non-prime numbers as it will check whether it is divisible by 2, if not it is a prime number

CodePudding user response：

This logic:

        for n in range(2, current_max   1):
            if(i%n == 0):
                break
            else:
                primes_sum  = i
                print(i)
                break

doesn't work to detect prime numbers, because if the first value of n you test (which will be 2) isn't a factor, you'll immediately count it as a prime and break the loop. You need to finish iterating over the entire range before deciding a number is a prime:

        for n in range(2, current_max   1):
            if i % n == 0:
                break
        else:
            primes_sum  = i
            print(i)

Note that the else is part of the for, not the if -- it only executes if the for loop exhausts itself without ever hitting a break (i.e. if it doesn't find any n values that are factors of i).

CodePudding user response：

The reason is perfectly explained by @SAI SANTOSH CHIRAG. I won't copy that. I'm not sure why you're using sqrt of a number. You can do the stuff without sqrt. You would get wrong output if you use sqrt. In your case, if we check for sqrt of 18, then int of it would be 4 and the divisibility is checked from 2 to 4 whereas 18 is also divisible by 6. I am designing a new code without sqrt and explaining it as well.

My logic: define a function that takes upper bound and lower bound as parameter. Take a for loop ranging from lower bound to upper bound. Now each value will be a number between the range. We've to check whether the number is prime. Use loop ranging from 2 to number and check whether it is divisible or not. If yes, it is not prime. If no, add it to sum. Your code:

def primes(low,upp):
    su=[]
    for i in range(low,upp 1):
        f=True
        for j in range(2,i):
            if i%j==0:
                f=False
        if f:
            su.append(i)
    return su,sum(su)
print(primes(10,20))