前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >求1000000以内的素数

求1000000以内的素数

作者头像
Tyan
发布2019-05-25 23:32:41
1.3K0
发布2019-05-25 23:32:41
举报
文章被收录于专栏:SnailTyan

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://cloud.tencent.com/developer/article/1434108

文章作者:Tyan

博客:noahsnail.com | CSDN | 简书

1. 素数

质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。大于1的自然数若不是素数,则称之为合数。

2. 求1000000以内的素数

  • 方法一 遍历法
代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <time.h>
#define NUM 1000000
using namespace std;
int main() {
    int i, j;
    clock_t start, end;
    double duration;
    start = clock();
    for(i = 2; i <= NUM; i++) {
        for(j = 2; j < i; j++) {
            if(i % j == 0) {
                break;
            }
        }
        if(j == i) {
            printf("%d\n", i);
        }
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("%f seconds.\n", duration);
    return 0;
}

分析:上面的方法最容易想到,但同时效率也最低。其运行时间:133.186849 seconds.

  • 方法二 在上面的基础上进行改进
代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <time.h>
#define NUM 1000000
using namespace std;
int main() {
    int i, j;
    clock_t start, end;
    double duration;
    start = clock();
    printf("%d\n", 2);
    for(i = 3; i <= NUM; i += 2) {
        for(j = 3; j < i; j += 2) {
            if(i % j == 0 || j * j > i) {
                break;
            }
        }
        if(j * j > i) {
            printf("%d\n", i);
        }
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("%f seconds.\n", duration);
    return 0;
}

分析:在上面的基础上,首先我们可以确定除了2之外的偶数都可以排除,同时如果执行到某个数的平方根(邻近的整数)都不能被其整除,则其后的数字都不能被其整除,如果可以整除,则另一个因子必定在平方根之前的数中。其运行时间:0.194340 seconds.

  • 方法三 筛法
代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <time.h>
#define NUM 1000000
using namespace std;

bool is_prime[NUM + 1];
int main() {
    clock_t start, end;
    double duration;
    start = clock();
    for (int m = 2; m < NUM; m++) {
        is_prime[m] = true;
    }
    for(int i = 2; i <= NUM; i++) {
        if(is_prime[i]) {
            for(int j = 2 * i; j < NUM; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for(int i = 2; i <= NUM; i++) {
        if(is_prime[i]) {
            printf("%d\n", i);
        }
    }
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("%f seconds.\n", duration);
    return 0;
}

分析:筛法是指假设所有数都为素数,然后遍历,如果其为素数,则其倍数皆为和数,遍历所有数即可。其运行时间:0.021246 seconds.

总结:从上面的运行时间可以看出,不同的方法运行时间差异非常大,代码要注意优化。

参考资料

  1. 程序设计与算法(一)
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年01月09日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 素数
  • 2. 求1000000以内的素数
  • 参考资料
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档