素数筛选高效算法

妖狐艹你老母 2021-11-02 14:32 354阅读 0赞

用普通的筛法，1000 0000 的数，需要用时1600ms左右。

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    
    char dp[10000010];
    
    const int inf = 10000001;
    int t = sqrt(inf);
    
    inline void  prime (   )
    {
         
    int i, j, k = 0,p;
      dp[1] = -1;
    for (i = 2; i <= t; i++)
    if( dp[i] != -1)
        {
         
    //p = inf / i;
        for (j = 2; j <= inf / i  ; j ++)
            dp[i * j] = -1;
        }
    }
    
    int main( )
    {
         
    int N, k, i;
      prime (  );
    while(scanf("%d", &N) != EOF)
      {
         
    
    
    for  (i =2; i < N; i++)
    if (dp[i]!= -1)
          printf("%d\n",i);
       }
    return 0;
      }

而用如下筛法,则只需440ms左右。强大啊，也只需要开500 0000的数组。偶数不用筛了，筛过的也不用筛了。(thanks  tao  -\_-) .

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    
    int dp[5000010] = {
         0};
    
    int main( )
    {
         
    int N,i, j, k, n;
    while (scanf("%d", &N) != EOF ) {
         
        n = sqrt( N +1);
    for ( i = 3;i <= n; i += 2) {
         
    if (dp[i >> 1])
    continue;
    int x = i << 1;
    for( j = i * i; j <= N; j += x)
                dp[j >> 1] = 1;
        }
                 printf("2\n");    
    int t = (N +1) / 2;
    for ( i = 1; i < t ; i++)  {
         
    if(dp[i]) 
    continue;
                 printf("%d\n",(i << 1 )+ 1);
            }
    }
    return 0;    
    
    }

转载于:https://www.cnblogs.com/tangcong/archive/2011/07/21/2113305.html

发表评论取消回复

表情：

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

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

相关阅读

相关筛选法求素数（高效）——例题：孪生素数问题

描述写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了

心已赠人/ 2022年06月13日 11:59/ 0 赞/ 320 阅读

相关求素数（普通+筛选）

一般求解n以内素数的算法。时间复杂度是o(n\sqrt(n)),当n较小时可以用。代码： ![Center][] 当n较大时，一般选用埃氏筛选法，时间复杂度o(n

逃离我推掉我的手/ 2022年06月11日 08:23/ 0 赞/ 246 阅读

相关线性筛选素数

/ @author liu / public class Main{ public static void main(String[] args) { final

男娘i/ 2022年06月02日 03:06/ 0 赞/ 192 阅读

相关素数三元组-南阳OJ1156（高效打表筛选）

素数三元组时间限制：1000 ms | 内存限制：65535 KB 难度：1 描述相邻三个奇数都是素数是一种非常少见的情形，也就是三个奇数p-2, p, p+

我会带着你远行/ 2022年06月01日 03:42/ 0 赞/ 138 阅读

相关埃拉托斯特尼筛法（素数高效筛选）

一、素数定义素数又称质数（prime number），指所有大于1的数中只能被1和它本身整除的数。二、埃拉托斯特尼筛法（Sieve of Eratosthenes

╰半夏微凉°/ 2022年05月25日 01:56/ 0 赞/ 272 阅读

相关素数的高效算法

素数最简单的判断方法是采用枚举，复杂度为O（n）。（这里不作解释）这里将介绍下列几点： 1）素数判断，复杂度为O（√n）的原理及代码。 2）素数表的获取。 3）

水深无声/ 2022年04月24日 07:36/ 0 赞/ 218 阅读

相关【算法】Eratosthenes筛选法与欧拉筛选法求素数

Eratosthenes筛法 1.原理一个合数可以分成几个素数的和，如果把素数(最初只知道2)的倍数全都去掉，剩下的就都是素数了 2.思路分析 1. 去

港控/mmm°/ 2022年04月01日 04:12/ 0 赞/ 341 阅读

相关算法：素数筛选

include <stdio.h> include <stdlib.h> int main(void) { //这个是输出1000以内的

Love The Way You Lie/ 2022年03月20日 15:58/ 0 赞/ 279 阅读

相关筛选法求素数

int vis[1000]; //记录标记 int p[1000]; //存素数 int main() { int n,i

系统管理员/ 2022年03月10日 07:45/ 0 赞/ 325 阅读

相关素数筛选高效算法

用普通的筛法，1000 0000 的数，需要用时1600ms左右。 include <stdio.h> include <string.h> incl

妖狐艹你老母/ 2021年11月02日 14:32/ 0 赞/ 355 阅读