Swift 计数质数 - LeetCode

LeetCode.jpg

题目:计数质数

描述:统计所有小于非负整数 n 的质数的数量。

案例1:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

质数的定义:质数

方案一:判断质数
代码一:
func countPrimes(_ n: Int) -> Int {
    if n < 3 {
        return 0
    }
    
    var count = 1
    //判断大于3的奇数
    for i in 3..<n where i % 2 != 0 {
        if isPrime(i) {
            print(i)
            count += 1
        }
    }
    return count
}

func isPrime(_ n: Int) -> Bool {
    //为了下面的for循环能正常进行,在这里加这个判断,只有3不满足下面循环条件
    if n == 3 {
        return true
    }
    //对N开根号
    for i in 2...Int(sqrt(Double(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}
执行用时:4812ms、、、真是慢啊,要是上面条件直接是n或者n/2提交直接超时
方案二:筛法
代码二:
func countPrimes(_ n: Int) -> Int {
    if n < 3 {
        return 0
    }
    if n == 3 {
        return 1
    }
    var array = [Bool](repeating: true, count: n)
    
    for i in 2...Int(sqrt(Double(n))) {
        if i * i >= n { break }
        if !array[i] { continue }
        var j = i * i
        while j < n {
            array[j] = false
            j = j + i
        }
    }
    var count = 0
    for i  in 2..<n {
        if array[i] {
            count += 1
        }
    }
    return count
}

执行用时:420ms

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 不用加减乘除做加法

892
来自专栏机器学习实践二三事

leetcode之-题17

题目 Given a digit string, return all possible letter combinations that the numbe...

1988
来自专栏木子昭的博客

寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1) 异或运算 两个相同...

2665
来自专栏swag code

swap()交换两个变量的方法汇总

1044
来自专栏C/C++基础

不用加号实现两整数相加

对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来...

592
来自专栏AILearning

简单的排序算法

细细一看,我们就明白了为什么这样写的! import java.util.*; class Sort { public static void main(S...

20510
来自专栏Hongten

java多线程系列_使用Runnable接口创建线程(3)

实现Runnable接口的类必须使用Thread类的实例才能创建线程。通过Runnable接口创建线程分为两步:

873
来自专栏WD学习记录

牛客网 二进制中1的个数

932
来自专栏程序生活

Leetcode-Easy 796. Rotate String

796. Rotate String 描述: 有两个字符串A和B,将A的第一个字符左移到最后位置,判断此时A是否等于B,如果等于返回true。不等于则继续左...

2905
来自专栏java学习

面试题42(在JAVA中,下列哪些是Object类的方法)

在JAVA中,下列哪些是Object类的方法? ---- A synchronized() B wait() C notify() D notifyAll()...

4606

扫码关注云+社区

领取腾讯云代金券