Count Prime in Swift (Following Sieve of Eratosthenes Algo)


  • 0
    S
    // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    
    class Solution {
        func countPrimes(_ n: Int) -> Int {
    
            // var odd numbers are prime , even numbers are not.
              if n <= 2 { return 0 }  
    
            //create an array to hold all n number
              var isPrime:[Bool] = []
    
            //for every even number set it as notPrime
              for i in 0..<n
              {
                  if i%2 == 0 { 
                      isPrime.append(false) 
                  }
                  else {
                      isPrime.append(true)
                  }
              }
    
              var count = 1  //Count = 1 to account for number 2
    
            // Initialize at 3 
              var num = 3
              while num < n{
                  if isPrime[num] == true {
                      count+=1
                      var j = num
    
                      //set all the number to follow which are a multiple of j
                      while j*num < n{
                          isPrime[num*j] = false
                          j+=2
                      }
    
                  }
                  num += 2  //plus 2 each time(to skip even ones as its already set above)
              }
              return count
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.