快速求小于N的所有素数

我会带着你远行 2022-06-08 01:07 236阅读 0赞

首先，贴上实现的源代码：

//
    //  main.cpp
    //  testC++1
    //
    //  Created by fei dou on 12-7-26.
    //  Copyright (c) 2012年 vrlab. All rights reserved.
    //
    
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    void primeLessThanN( int n)
    {
        if(n < 1) return ;
        bool *isPrime = new bool[n+1];//动态生成一个数组
        memset((void*)isPrime, true, (n + 1)*sizeof(bool));
        
        int sqrtOfN = sqrt(n);
        isPrime[0] = false;
        isPrime[1] = false;
        for( int i = 0; i <= sqrtOfN; ++ i )
            if(isPrime[i] == true)
                for(int j = i*i; j <= n; j +=i)
                    isPrime[j] = false;
        
        int count = 0;
        for(int m = 0; m <= n ; m ++)
        {
            if(isPrime[m] == true)
            {
                printf("%-5d    ",m);
                ++ count;
                
                if( count % 5 == 0 )
                    printf("\n");
            }
        }
        
        delete[] isPrime;//释放空间
    }
    
    int main (int argc, const char * argv[])
    {    
        primeLessThanN(32768);
        return 0;
    }

本程序使用的是Sieve of Eratosthenes方法，这是一种快事求取小于N的所有素数的方法。

它的具体原理可以参考：http://en.wikipedia.org/wiki/Eratosthenes\_Sieve

如果有什么不太名白的地方可以给我留言，大家一起探讨！

发表评论取消回复

表情：

评论列表（有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

相关求n以内的所有素数并输出

include<stdio.h> include<stdlib.h> include<math.h> //求n以内的所有素数 int

迷南。/ 2022年08月07日 11:58/ 0 赞/ 213 阅读

相关 Eratosthenes筛选法求小于N的所有素数个数

求出1~N范围中所有的素数，在leetcode中做过这个题目，我想从对每个1~N进行一次遍历，每个数判断一次是否是素数。判断一个数是否是素数的复杂度本身也是挺高的，再进行一

叁歲伎倆/ 2022年07月12日 03:22/ 0 赞/ 233 阅读

相关 Eratosthenes筛选法求小于N的所有素数个数

求出1~N范围中所有的素数，在leetcode中做过这个题目，我想从对每个1~N进行一次遍历，每个数判断一次是否是素数。判断一个数是否是素数的复杂度本身也是挺高的，再进行一

港控/mmm°/ 2022年07月12日 03:22/ 0 赞/ 213 阅读

相关 java 找出小于数字N的所有素数

代码如下所示： package test3; import java.util.Scanner; / 找出小于数字N的

悠悠/ 2022年06月17日 12:15/ 0 赞/ 221 阅读

相关快速求小于N的所有素数

首先，贴上实现的源代码： // // main.cpp // testC++1 // // Created by fei dou

我会带着你远行/ 2022年06月08日 01:07/ 0 赞/ 237 阅读

相关算法性能比较（一）——找出小于等于n的所有素数

算法性能比较系列文章主要用于记录笔者刷题时自己写的算法与最佳算法之间的性能比较。计算素数一般会用下面这样的算法： function isPrimeNum(num)

末蓝、/ 2022年05月31日 04:19/ 0 赞/ 226 阅读

相关输出n以内的所有素数

问题C：C / C ++经典程序训练7 ---求某个范围内的所有素数时间限制：1秒内存限制：64 MB 提交：1766解决：561 \[ [提交][Link 1

╰半橙微兮°/ 2022年05月27日 08:35/ 0 赞/ 237 阅读

相关输入一个整数n，求小于这个整数的所有质数。

算法：定义一个长度为n的boolean数组，true表示是质数，false表示不是质数。初始化为true,之后从2开始循环。步骤： I、找到第一个值为true

淡淡的烟草味﹌/ 2022年05月20日 05:59/ 0 赞/ 271 阅读

相关输入一个自然数n，求小于等于n的素数之和？

问题描述：输入一个自然数n，求小于等于n的素数之和；例如：样例输入：2 样例输出：2。解题思路：（1）什么是素数：素

痛定思痛。/ 2022年05月17日 11:38/ 0 赞/ 279 阅读

相关求出1-N中的所有素数，不连N算。

import java.util.Scanner; public class Main \{ public static void main(String\[\] ar

矫情吗；*/ 2022年04月22日 11:24/ 0 赞/ 220 阅读