I wrote this python code about 3 days ago, and I am stuck here, I think it could be better, but I don't know how to improve it. Can you guys please help me?
# Function
def is_prime(n):if n == 2 or n == 3:return Truefor d in range(3, int(n**0.5), 2):if n % d == 0:return Falsereturn True
A good deterministic way to find relatively small prime numbers is to use a sieve.
The mathematical principle behind this technique is the following: to check if a number is prime, it is sufficient to check that it is not divisible by other primes.
import mathdef is_prime(n):# Prepare our Sieve, for readability we make index match the number by adding 0 and 1primes = [False] * 2 + [True] * (n - 1)# Remove non-primesfor x in range(2, int(math.sqrt(n) + 1)):if primes[x]:primes[2*x::x] = [False] * (n // x - 1)return primes[n]# Or use the following to return all primes:# return {x for x, is_prime in enumerate(primes) if is_prime}print(is_prime(13)) # True
For reusability your could adapt the above code to return the set
of all prime numbers up to n
.