`
kmplayer
  • 浏览: 509801 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

改进的线性筛法_寻找素数

阅读更多
1,实例代码:
#include <iostream>
using namespace std;

const int MAX=100;
bool isPrime[MAX+1];
int total;//计数
int prime[MAX+1];

//线性筛法寻找素数
void makePrime()
{
    memset(isPrime,true,sizeof(isPrime));
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=MAX;i++)
    {
        if(isPrime[i]) prime[total++]=i;
        for(int j=0; j<total && i*prime[j]<=MAX; j++)
        {
            isPrime[i*prime[j]]=false;
            //i此时不是素数,只是拓展用
            if(i%prime[j]==0) break;
        }
    }
}

int main()
{
    makePrime();
    for(int i=0;i<total;i++)
    {
        cout<<prime[i]<<" ";
        if((i+1)%10==0) cout<<endl;
    }
    return 0;
}
分享到:
评论

相关推荐

    matlab算法源码MATLAB寻找素数源码

    还有一种是基于欧拉筛法的改进算法,也称为线性筛法。这种方法不仅能够找出小于N的所有素数,而且能够保证每个合数只被它的最小素因子筛选一次。线性筛法具有时间复杂度较低的特点。 对于Matlab来说,实现这样的...

    计算素数个数的一个新公式

    后来,数学家们改进了这种筛法,提出了一些更为复杂的算法,如线性筛法和概率筛法等,以期更高效地找出素数或者估计素数的个数。 在素数计数研究领域,除了素数定理之外,还涉及到其他一些数学概念和定理,例如黎曼...

    MATLAB find 素数_matlab_

    标题中的“MATLAB find 素数_matlab_”指的是使用MATLAB编程语言寻找素数的方法。MATLAB是一种强大的数学计算软件,它提供了丰富的函数和工具来处理各种数学问题,包括寻找素数。 在数学中,素数是大于1且除了1和其...

    ACM中的数学问题PPT教学课件.pptx

    改进后的筛法在空间复杂度上保持线性,同时减少了不必要的重复操作。 最后,课件提到了欧拉函数,它是计算小于等于一个数x并与x互质的正整数个数的函数,记作φ(x)。欧拉函数有三个重要的性质:对于素数p,φ(p) = ...

    zhishu.rar_1直100的zhishu

    4. **线性筛法**:在埃拉托斯特尼筛法的基础上优化,避免重复计算,适用于大范围的质数查找。 在“改动运行次数,能够求出随意的质数”这一描述中,意味着这个程序可能具有灵活性,可以适应不同的质数范围。这可能...

    F.c.zip_The Prime

    根据描述,这个项目可能采用了某种优化过的线性算法,可能是改进版的埃拉托斯特尼筛法或者一种更现代的快速素数检测技术。然而,具体实现需要查看源代码"**F.c**"才能得知。 总结来说,《F.c.zip_The Prime》项目...

    PrimeTest

    例如,轮换法和线性筛法是在已知素数基础上改进的算法,适用于大规模素数生成。 7. **素数分布**:素数在自然数中的分布并不均匀,素数定理描述了素数密度随数字增加而减少的趋势。了解素数的分布规律有助于理解和...

    ACM数论(挺好理解的)

    - **Euler筛法**: Euler筛法是一种改进的筛法,它利用了积性函数的性质来优化筛选过程。 - **伪代码**: ```plaintext for i in range(2, n+1): if p[i] is undefined: prime.add(i) for q in prime: if i*q &gt; ...

    ACM试题集 经典试题集

    - 筛法是构建素数表的经典方法之一,如埃拉托斯特尼筛法等。 - 筛法通过排除已知的合数来逐渐找出素数。 **4. 素数随机判定(Miller-Rabin)** 问题描述:判断一个大数是否为素数。 算法思路: - Miller-Rabin...

    清华内部ACM培训资料_各类经典算法

    6. **筛法素数生成器**:通过埃拉托斯特尼筛法生成素数列表。 7. **素数判断**:确定一个整数是否为素数。 **图论**: 1. **Prim 算法**:用于寻找加权无向图的最小生成树。 2. **Dijkstra 算法**:单源最短路径...

    经典算法源代码(for ACM)

    **筛素数[1..N]**:使用埃拉托斯特尼筛法或其他筛选方法找出指定范围内的所有素数。 **高效求小范围素数[1..N]**:优化筛法,减少不必要的计算。 **随机素数测试(伪素数原理)**:通过概率性的测试来判断一个数是否...

    ACM经典代码_相当不错的资料.pdf

    生成素数表的方法通常包括埃拉托斯特尼筛法等。 ##### 4. 素数随机判定(miller_rabin) Miller-Rabin素性测试是一种基于概率的素数检测算法。该算法可以在多项式时间内给出一个数可能是素数的概率估计。虽然它不能...

    ACM常用算法代码 pdf

    - **实现方法**: 使用埃拉托斯特尼筛法生成。 **4. 素数随机判定(Miller-Rabin)** - **定义**: Miller-Rabin测试是一种用于确定一个给定整数是否为素数的概率性算法。 - **应用场景**: 当需要快速判断大整数是否为...

    上海交大ACM模板,ACMer值得一看

    常见的算法有埃拉托斯特尼筛法和线性筛法等。 #### 3.4 欧拉函数 (Phigenerator, Eular Function) 欧拉函数φ(n)是指不大于正整数n且与n互质的正整数个数。它可以用来解决很多与数论有关的问题。 #### 3.5 离散...

    ACM比赛模板

    筛法素数产生器是一种生成一定范围内素数列表的有效方法,其中最著名的是埃拉托斯特尼筛法。 **7. 判断一个数是否素数** 判断一个数是否为素数可以通过试除法或更高级的方法如米勒-拉宾素性检验来实现。 #### 五...

    acm资料(比较常用的算法实现代码)

    6. **筛法素数产生器**:埃拉托斯特尼筛法找出一定范围内的素数。 7. **判断一个数是否素数**:可以使用试除法或更高级的Primality Test。 8. **求子距阵最大和**:Kadane's algorithm 或其他动态规划策略。 9. **求...

Global site tag (gtag.js) - Google Analytics