当前位置:   article > 正文

【算法】普通方法和筛选法求素数_普通筛选法求素数

普通筛选法求素数

素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数运行得非常快。下面首先介绍如何判断一个是不是素数,然后介绍用普通方法求n以内的素数,接着是筛选法求n以内的素数,最后是两种算法的运行时间比较

判断一个数是不是素数

算法思想:判断小于等于一个数的平方的所有大于1的整数是不是能整除这个数,如果能,则表明这个数不是素数;反之,则是素数。

//判断一个数是否为素数 
bool isPlain(int value){
    int m = sqrt(value);
    if (value < 2) return false;
    for (int i = 2; i <= m; i++){
        if ((value%i)==0){
            return false;
        }
    }
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

普通方法求解n以内的素数

算法思想:声明一个n大小的bool数组,初始值为false,然后从2开始判断一个数是否为素数,若是,则将其的布尔值定为true

//普通法求素数
bool* putong(int n){
    bool* value = new bool[n];
    for (int i = 0; i < n; i++)
        value[i] = false;
    for (int i = 2; i < n; i++){
        if (isPlain(i)){
            value[i] = true;
        }
    }
    return value;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

筛选法求n以内的素数

算法思想:找出小于等于n的开方的素数,然后将n内所有这些素数的倍数统统去掉,剩下的数就都是素数,也是通过布尔数组实现

//筛选法求素数
bool* shuaixuan(int n){
    bool* value = new bool[n];
    for (int i = 0; i<n; i++)
        value[i] = true;

    value[0] = false;
    value[1] = false;

    for (int i = 2; i <= sqrt(n); i++){
        if (value[i] && isPlain(i)){
            int c = 2;
            int j = i*c;
            while (j < n){
                value[j] = false;
                j = i*c++;
            }
        }
    }
    return value;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

完整代码及运行结果

下述代码分别调用了普通方法和筛选法,可循环输入n(按Ctrl + C结束),以供不同数据的测试,后面附了一张运行测试的结果图

#include <iostream>
using namespace std;
#include <ctime>
#include <math.h>
#include <conio.h>
//判断一个数是否为素数 
bool isPlain(int value){
    int m = sqrt(value);
    if (value < 2) return false;
    for (int i = 2; i <= m; i++){
        if ((value%i)==0){
            return false;
        }
    }
    return true;
}

//普通法求素数
bool* putong(int n){
    bool* value = new bool[n];
    for (int i = 0; i < n; i++)
        value[i] = false;
    for (int i = 2; i < n; i++){
        if (isPlain(i)){
            value[i] = true;
        }
    }
    return value;
}

//筛选法求素数
bool* shuaixuan(int n){
    bool* value = new bool[n];
    for (int i = 0; i<n; i++)
        value[i] = true;

    value[0] = false;
    value[1] = false;

    for (int i = 2; i <= sqrt(n); i++){
        if (value[i] && isPlain(i)){
            int c = 2;
            int j = i*c;
            while (j < n){
                value[j] = false;
                j = i*c++;
            }
        }
    }
    return value;
}

int main(){

    int n;
    while (cin >> n){

        int start = clock();
        bool* value1 = putong(n);
        int end = clock();
        cout << "普通方法:" << end - start << endl;

        start = clock();
        bool* value2 = shuaixuan(n);
        end = clock();
        cout << "筛选法:" << end - start << endl;

        delete[] value1;
        value1 = NULL;
        delete[] value2;
        value2 = NULL;
    }
    _getch();
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

这里写图片描述
从图中可看出,n越大,筛选法对普通方法的性能就越好。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/775097
推荐阅读
相关标签
  

闽ICP备14008679号