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

素数指的是因子只有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;
}

普通方法求解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;
}

筛选法求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;
}

完整代码及运行结果

下述代码分别调用了普通方法和筛选法,可循环输入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();
}

从图中可看出,n越大,筛选法对普通方法的性能就越好。

时间: 03-30

【算法】普通方法和筛选法求素数的相关文章

筛选法求素数

筛选法求素数,不断的用3,5,7,等素数作为筛子,筛除这些数的倍数,即将合数筛除.用辅助数组p记录数i是否是素数. vector<int> prime(int n) { vector<int> p(n+1); for(int i=2;i<=n;i+=2) { if(i%2==0&&i>2) p[i]=0; else p[i]=1; } for(int i=3;i<=(int)(sqrt((double)n));i+=2) { if(p[i]) fo

hdu how many prime numbers 筛选法求素数

/* * hdu How many prime numbers * date 2014/5/13 * state AC */ #include <iostream> #include <cmath> #include <cstdio> using namespace std; bool isPrime(int x) { int sqr=sqrt(x*1.0); for(int i=2;i<=sqr;i++) { if(x%i==0)return false; }

Facebook Hacker Cup 2015 Round 1--Homework(筛选法求素数)

题意:给定A,B,K(A<=B)三个数,问在[A,B]范围内的数素数因子个数为K的个数. 题解:典型的筛选法求素数.首先建立一个保存素数因子个数的数组factorNum[],以及到n为止含有素数因子个数为k的二维数组sumNum[n][k]. factorNum可以由筛选法确定,初始化数组为0. 1. 从小到大遍历给定最大范围内的数,若遍历到数n时,factorNum[n]=0则说明这个数是素数(前面没有它的因子). 2. 然后通过增加n的倍数,来筛选出最大范围内含有素数因子n的数. sumNu

java筛选法求素数

这本身没什么,代码一堆 发来纪念下而已 本来刚学习java,编写输出100以内的素数 对于我这个有代码运行性能洁癖的人(但是本身又不懂算法)来说,不能忍 于是看了些资料 参考: http://blog.csdn.net/program_think/article/details/7032600 自己山寨一个 (注意是山寨,那就是抄袭改改而已) public class TestPrime{ // 程序的入口 public static void main(String args[]){ // 向

HDU 2136 Largest prime factor (筛选法求素数)

Largest prime factor Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7297    Accepted Submission(s): 2589 Problem Description Everybody knows any number can be combined by the prime number. Now

P168 筛选法求素数

#include <stdio.h>int main(){ int n,i,j,h=0; scanf("%d",&n); for(i=2;i<=n;i++) {  for(j=2;j<=i;j++)    {   if((i%j==0)&&(i!=j)) break;     else {printf("%d\n",i);break;} } }return 0;}

筛选法&lt;求素数表&gt;

如果题目的数据规模较大,常规地逐个判断素数的方法行不通,可以使用筛选法进行预处理,将所有素数一次性求出并存入数组中. 筛选法求素数的主要思想如下: (1)将1~N的所有数都标记为素数,0表示素数,1表示非素数. (2)1不是素数,也不是合数,标记为1. (3)2是素数,保留.但比2大的所有2的倍数都标记为1,直到大于N为止. (4)继续寻找素数标记,找到3,将其保留,但比3大的所有3的倍数都标记为,直到大于N为止. -- tip:如果数组声明为全局变量,那么数组会初始化为全0,所以我没有定义in

用筛选法求100以内的素数(数组)

用筛选法求100以内的素数,要求使用数组. #include "stdafx.h" #include<iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int a[100],i,b[100],j,n=0;     //数组a[100]来放用于判断的数,数组b[100]来放素数 for(i=0;i<100;i++)       //注意这里i不能从1开始,因为数组a的首位是a[0]

hdu2824 The Euler function 筛选法求欧拉函数模板题

//求a , b范围内的所有的欧拉函数 //筛选法求欧拉函数模板题 #include<cstdio> #include<cstring> #include<iostream> using namespace std ; const int maxn = 3000010 ; typedef __int64 ll ; int e[maxn] ; int a ,  b ; void Euler() { int i,j; for (i=1;i<maxn;i++) e[i]