+ 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)!

26th Nov 2020, 7:07 PM
Md. Niamul Ahad Chowdhury
Md. Niamul Ahad Chowdhury - avatar
2 Answers
+ 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.
26th Nov 2020, 7:26 PM
Shadow
Shadow - avatar
+ 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.
26th Nov 2020, 7:37 PM
Md. Niamul Ahad Chowdhury
Md. Niamul Ahad Chowdhury - avatar