专栏首页Bingo的深度学习杂货店素数(质数)筛选法模板

素数(质数)筛选法模板

判断一个数是否为质数

int is_prime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return 0; // 不是质数
        }
    }
    return 1; // 是质数
}

素数筛选法(时间复杂度O(nlogn))

for (int i = 2; i <= n; ++i) {
    is_prime[i] = 1;
}
for (int i = 2; i <= n; ++i) {
    for (int j = i * 2; j <= n; j += i) {
        is_prime[j] = 0;
    }
}
for (int i = 2; i <= n; ++i) {
    is_prime[i] = 1;
}
for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = 0;
        }
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 几道暑期实习笔试题

    DFS 回溯法,先判断组成三连对和组成顺子需要的次数,递归深度 k 就是次数。对于对子和单张的可以直接通过枚举数需要打多少次。可以在组成三连对和顺子的时候增加剪...

    echobingo
  • 搜索与回溯算法模板及其应用

    为了求得问题的解,先选择某一种可能情况向前探索,在探索的过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解...

    echobingo
  • Q191 Number of 1 Bits

    Write a function that takes an unsigned integer and returns the number of ’1' bi...

    echobingo
  • Leetcode 60. Permutation Sequence

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • 爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

    例如上图, 则H的祖先个数是3个(包括它自己哈),分别是和. 而N的祖先个数是4()。

    ACM算法日常
  • 排序算法的实现与比较

    Zoctopus
  • JAVA 练习 找出素数

    拾点阳光
  • 操作系统实验四代码

    Ewdager
  • 【leetcode刷题】T40-根据字符出现频率排序

    Given a string, sort it in decreasing order based on the frequency of characters...

    木又AI帮
  • C++核心准则ES.42: 使用指针时要简单且直接

    Complicated pointer manipulation is a major source of errors.

    面向对象思考

扫码关注云+社区

领取腾讯云代金券