Prime number function loop mistake [closed]

1
votes

I have been told that this code for finding a prime number is wrong. Could anyone explain why? It works for at least the first 100 numbers.

    if x<2:
        return 'It is neither prime nor composite'
    elif x==2 or x==3:
        return 'It is a prime number'
    else:
        for i in range(2,int(x**0.5)+1):
            print(i)
            if x%i==0 :
                
                return 'It is not a prime number'
                break
        else:
            return 'It is a prime number'
2
pythonfunctionloopsprimes
Can you explain why not Riccardo? The logic looks okay to me, but maybe I'm missing something obvious. Note that the input is a single number (x) and the output is whether it is prime or not – Chris
@shravya, the person who told you it was wrong, did they give any reasons? Is it maybe that the requirements were different, were you expected to list all primes in a given range? – Chris
Exactly - I'm arguing the case that it appears correct to me - Riccardo said that the function failed for input 33 but I think he may have removed that comment now! – Chris
Now he has removed all his comments leaving mine without any context - I'll remove mine to avoid confusion - sorry @interjay, now your comment doesn't have context, it's why deleting comments without warning is a bit of a pain – Chris
@Shrvya, maybe this line - for i in range(3, int(n ** 0.5)+1, 2): Why not starting with 3 in the range? Because it will save a lot of computations... – Daniel Hao

2 Answers

1
votes

I've tested your function with 1,000,000 integers, starting from 2, by comparing your results with ones from dedicated function from sympy library.

import sympy

def prime(x):
    if x<2:
        return False
    elif x==2 or x==3:
        return True
    else:
        for i in range(2,int(x**0.5)+1):
            # print(i)
            if x%i==0 :
                return False
                # break  # not necessary, "return" above exits anyway
        else:
            return True

success = 0
fail = 0
for i in range(2, 1000002):
    if prime(i) != sympy.isprime(i):
        print(i)
        fail += 1
    else:
        success += 1
print(f'SUCCESSES: {success}\nFAILURES: {fail}')

Output:

SUCCESSES: 1000000
FAILURES: 0

You function seems to work with no issues

1
votes

Perhaps, it was meant not incorrectness, but inefficiency of the code. I would write differently:

def prime(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    d = 3
    while d**2 <= n:
        if n % d == 0:
            return False
        d += 2
    return True

print(*filter(prime, range(101)))