[Question]: Check if given number is prime ? Prime numbers are divisible by self & 1 only
Example prime number : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59
#Approach 1: if the number is perfectly divisible by 2,3,5 Then it’s not prime.
func checkIfNumberIsPrime(_ n : Int) ->Bool {
if n <= 1 {return false}
if n == 2 || n == 3 || n == 5 {return true}
return !(n%2 == 0 || n%3 == 0 || n % 5 == 0)
}
let n = 7
let isPrime = checkIfNumberIsPrime(n)
print("The number is- ", isPrime) // trueApproach #2: Take a square root of the number & check from 2 onwards if it’s perfectly divisible it’s not prime.
func checkIfNumberIsPrime(_ n : Int) ->Bool {
if n <= 1 {return false}
for i in 2..<Int(sqrt(Double(n))) {
if i%2 == 0 { return false }
}
return true
}class Solution {
func countPrimes(_ n: Int) -> Int {
guard n > 2 else { return 0 }
var count = 0
var isPrimeArray = Array(repeating: true, count: n)
isPrimeArray[0] = false
isPrimeArray[1] = false
var current = 2
// Sieve of Eratosthenes algorithm
while current * current < n {
if isPrimeArray[current] {
var multiple = 2
while current * multiple < n {
isPrimeArray[current * multiple] = false
multiple += 1
}
}
current += 1
}
// Count the prime numbers
for i in 2..<n {
if isPrimeArray[i] {
count += 1
}
}
return count
}
}