Mathematical Algorithms | Prime Number
Checker
Data Structures and Algorithms
In this lecture, we will discuss prime numbers and how to determine whether a given number is prime
or not. A prime number is a positive integer greater than 1 that has no positive integer divisors other
than 1 and itself. For example, 13 is a prime number because it is only divisible by 1 and 13.
To check whether a number is prime or not, we can use a simple algorithm. We start by checking if the
number is less than 2. If so, we know it is not prime. Next, we check if the number is equal to 2, in which
case it is prime. If the number is even, we can also immediately determine that it is not prime since it is
divisible by 2. After that, we loop through all odd numbers less than or equal to the square root of the
given number. If the number is divisible by any of these odd numbers, then it is not prime. Otherwise, it
is prime.
Here is an implementation of this algorithm in Python:
import math
def is_prime(n):
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
limit = int(math.sqrt(n))
for i in range(3, limit+1, 2):
if n % i == 0:
return False
return True
In this implementation, we first check if the number is less than 2 and return False if so. Then, we check
if the number is 2 and return True if so. If the number is even, we return False. Finally, we loop through
all odd numbers less than or equal to the square root of the given number, checking if the number is
divisible by any of them. If so, we return False. If we make it through the loop without finding a divisor,
we return True.
It is worth noting that there are more efficient algorithms for testing primality, such as the Miller-Rabin
test or the AKS test. However, the algorithm described here is simple and works well for most practical
purposes.
Checker
Data Structures and Algorithms
In this lecture, we will discuss prime numbers and how to determine whether a given number is prime
or not. A prime number is a positive integer greater than 1 that has no positive integer divisors other
than 1 and itself. For example, 13 is a prime number because it is only divisible by 1 and 13.
To check whether a number is prime or not, we can use a simple algorithm. We start by checking if the
number is less than 2. If so, we know it is not prime. Next, we check if the number is equal to 2, in which
case it is prime. If the number is even, we can also immediately determine that it is not prime since it is
divisible by 2. After that, we loop through all odd numbers less than or equal to the square root of the
given number. If the number is divisible by any of these odd numbers, then it is not prime. Otherwise, it
is prime.
Here is an implementation of this algorithm in Python:
import math
def is_prime(n):
if n < 2:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
limit = int(math.sqrt(n))
for i in range(3, limit+1, 2):
if n % i == 0:
return False
return True
In this implementation, we first check if the number is less than 2 and return False if so. Then, we check
if the number is 2 and return True if so. If the number is even, we return False. Finally, we loop through
all odd numbers less than or equal to the square root of the given number, checking if the number is
divisible by any of them. If so, we return False. If we make it through the loop without finding a divisor,
we return True.
It is worth noting that there are more efficient algorithms for testing primality, such as the Miller-Rabin
test or the AKS test. However, the algorithm described here is simple and works well for most practical
purposes.
