+ 2
[SOLVED] Why does this primes algorithm fail ONLY for 323 and 214369?
import math as m def isprime(a): if a < 2 or a != 2 and a % 2 == 0 or str(a)[-1] == "5" and a != 5 or sum([int(i) for i in list(str(a))]) % 3 == 0 and a != 3: return(False) elif a == 2: return(True) else: for divisor in range(3, m.floor(m.sqrt(a))): if a % divisor == 0: return(False) return(True) # So far, fails ONLY for 323! print(isprime(323)) # prints "True" when this should not be! Update: 214369 also gives True; however, these are very exceptional cases (4/512 fails)!
2 ответов
+ 7
By rounding the square root down, you exclude it from the list of possible divisors since the range() function is exclusive on the right side, but you need to check the square root as well.
+ 3
Yes, as Shadow says, leaving out the square root was the error. Importantly, though, you would think that both solutions would work:
1. for divisor in range(3, 1 + m.floor(m.sqrt(a))):
2. for divisor in range(3, m.ceil(m.sqrt(a))):
But no, only the first one works, proving the devil is in the details.