精华内容
下载资源
问答
  • 找质数算法

    千次阅读 2010-08-03 20:18:00
    原文:http://www.cnblogs.com/guoxiaocong/archive/2005/12/27/305611.html 由于一个合数总是可以分解成若干个质数的乘积,那么如果把质数(最初只知道2是质数)的倍数都去掉,那么剩下的就是质数了。...

    原文:http://www.cnblogs.com/guoxiaocong/archive/2005/12/27/305611.html 由于一个合数总是可以分解成若干个质数的乘积,那么如果把质数(最初只知道2是质数)的倍数都去掉,那么剩下的就是质数了。例如要查找100以内的质数,首先2是质数,把2的倍数去掉;此时3没有被去掉,可认为是质数,所以把3的倍数去掉;再到5,再到7,7之后呢,因为8,9,10刚才都被去掉了,而100以内的任意合数肯定都有一个因子小于10(100的开方),所以,去掉,2,3,5,7的倍数后剩下的都是质数了。用程序可以这样解决,引入布尔类型数组a[i],如果i是质数,a[i]=true,否则a[i]=false。那么划掉i可以表示成a[i]=false。 //找出n以内质数 void Sieve(int n) { bool[] a = new bool[n+1]; for (int i = 2; i <= n; i++) a[i] = true; for (int i = 2; i <= Math.Sqrt(n); i++) { if (a[i]) for (int j = i; j*i <= n; j++) a[j * i] = false; } for (int i = 0; i <= n; i++) { if (a[i]) Console.Write("{0},",i.ToString()); } }

    展开全文
  • 找素数算法总结

    千次阅读 2012-06-06 23:31:34
    经典的素数判定算法是这样:给定一个正整数n,用2到sqrt(n)之间的所有整数去除n,如果可以整除,则n不是素数,如果不可以整除,则n就是素数。所以求小于N的所有素数程序如下:   #include  #include    #...
     
    

    问题描述:寻找素数 
    求小于自然数N的所有素数。

    解决方案

    程序 1-1 经典算法

    经典的素数判定算法是这样:给定一个正整数n,用2到sqrt(n)之间的所有整数去除n,如果可以整除,则n不是素数,如果不可以整除,则n就是素数。所以求小于N的所有素数程序如下:

     

    #include <stdio.h>

    #include <stdlib.h>

     

    #define N 1000000

     

    int main(int argc, char *argv[])

    {

      int m, n;

      for (n =2 ; n < N; n++)

      {

          for (m = 2; m * m <= n; m++)

               if (n % m == 0) break;

          if (m * m > n) printf("%6d",n);

      }

      system("PAUSE"); 

      return 0;

     

    算法的时间复杂度是O(N*sqrt(N)),求解规模较小的输入,尚且没有问题。但对于规模较大的N,算法就力不从心了。有一种算法叫厄拉多塞筛(sieve of Eratosthenes),它在求解时具有相当高的效率,但是要牺牲较多的空间。

     

    程序 1-2 厄拉多塞筛算法

    这个程序的目标是,若i为素数,则设置a[i] = 1;如果不是素数,则设置为0。首先,将所有的数组元素设为1,表示没有已知的非素数。然后将已知为非素数(即为已知素数的倍数)的索引对应的数组元素设置为0。如果将所有较小素数的倍数都设置为0之后,a[i]仍然保持为1,则可判断它是所找的素数。

     

    #include <stdio.h>

    #include <stdlib.h>

     

    #define N 1000000

     

    int a[N];

     

    int main(int argc, char *argv[])

    {

      int i, j;

      for (i = 2; i < N; i++) a[i] = 1;

      for (i = 2; i < N; i++)

      {

          if (a[i])

             for (j = i + i; j < N; j += i)

                 a[j] = 0;

      }

      for (i =2; i < N; i++)

          if (a[i]) printf("%6d ",i);

      system("PAUSE"); 

      return 0;

    }

     

    例如,计算小于32的素数,先将所有数组项初始化为1(如下第二列),表示还每发现非素数的数。接下来,将索引为2、3、5倍数的数组项设置成0,因为2、3、5倍数的数是非素数。保持为1的数组项对应索引为素数(如下最右列)。

    i                2       3       5       a[i]

    2       1                                   1

    3       1                                   1

    4       1       0                         

    5       1                                   1

    6       1       0      

    7       1                                   1

    8       1       0

    9       1                 0

    10     1       0

    11     1                                   1

    12     1       0

    13     1                                   1

    14     1       0

    15     1                 0

    16     1       0

    17     1                                   1

    18     1       0

    19     1                                   1

    20     1       0

    21     1                 0

    22     1       0

    23     1                                   1

    24     1       0

    25     1                          0

    26     1       0

    27     1                 0

    28     1       0

    29     1                                   1

    30     1       0

    31     1                                   1

     

    如何理解厄拉多塞筛算法呢?

    我们一定记得小学时候就学过的素数和合数的性质:任何一个合数一定可以表示成若干个素数之积。如:4 = 2 * 2,6 = 2 * 3,12 = 2 * 2 * 3。也就是说,合数N一定是小于N的某个(或若干)素数的整数倍,反之,如果N不是任何比它小的素数的倍数,则N必然是素数。

     

    程序 1-3 经典算法的改进版本

    经典素数判定算法中,并不需要用2到sqart(n)之间的所有整数去除n,只需要用其间的素数就够了,原因也是合数一定可以表示成若干个素数之积。算法的改进版本如下:

     

    #include <stdio.h>

    #include <stdlib.h>

     

    #define N 1000000

     

    int prime[N];

     

    int main(int argc, char *argv[])

    {

        int i, n, flag;

        prime[0] = 0; //保存素数的总个数

        for (n =2 ; n < N; n++)

        {

            flag = 1;

            for (i = 1; i <= prime[0] && prime[i] * prime[i] <= n; i++)

                if (n % prime[i] == 0)

                {

                    flag = 0;

                    break;

                }

            if (flag)

            {       

                prime[0]++;

                prime[prime[0]] = n;

                printf("%6d ",n);

            }

        }

        system("PAUSE");   

        return 0;

    }

     

    算法虽然在效率下,比先前版本有所提高,但需要牺牲空间记住已确定的素数。

     

    程序 1-4 厄拉多塞筛算法的改进版

    程序1-2使用一个数组来包含最简单的元素类型,0和1两个值,如果我们使用位的数组,而不是使用整数的数组,则可获得更高的空间有效性。

     

    #include <stdio.h>

    #include <stdlib.h>

     

    #define N 1000000

    #define BITSPERWORD 32 

    #define SHIFT 5

    #define MASK 0x1F

    #define COUNT 1+N/BITSPERWORD           //Bit i 对映数i

     

    void set(int a[],int i);

    void clr(int a[],int i);

    int test(int a[],int i);

     

    int  a[COUNT];

     

    int main(int argc, char *argv[])

    {

      int i, j;

      for (i = 0; i < COUNT; i++) a[i] = -1;

      for (i = 2; i < N; i++) {

          if (test(a,i))

             for (j = i + i; j < N; j += i)

                 clr(a,j);

      }

      for (i =2; i < N; i++)

          if (test(a,i)) printf("%4d ",i);

      system("PAUSE"); 

      return 0;

    }

     

    void set(int a[],int i) {

        a[i >> SHIFT] |= (1<<(i & MASK));

    }

     

    void clr(int a[],int i) {

        a[i >> SHIFT] &= ~(1<<(i & MASK));

    }

     

    int test(int a[],int i) {

        return a[i >> SHIFT] & (1<<(i & MASK));

    }

     

     

    展开全文
  • 下面以第1百万个素数为例子,观察算法分别的用时。 2、小白找素数 解释: 直接运用最简单的思维,根据一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数去写代码,效率低。出第1百万位素数...

    1、素数简介
    质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
    下面以找第1百万个素数为例子,观察算法分别的用时。

    2、小白找素数
    解释:

    直接运用最简单的思维,根据一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数去写代码,效率低。找出第1百万位素数 时间超过20分钟都没出结果。

    代码如下图:
    在这里插入图片描述
    3、小白(优化)找素数
    解释:

    根据上面的代码稍稍修改。判断该数是否是素数只需要检查2到根号n之间,因为如果d是n的约数,那么n/d也是n的约数,由n=d*(n/d)可知,d<=根号n,所以检查2到根号n之间是否有整数能整除n。找出第1百万位素数 运行时间88248毫秒等于1.4708分钟。

    代码如下图:

    在这里插入图片描述
    4、埃氏筛法求找素数
    解释:
    埃氏筛法运行原理:

    • 要得到自然数n以内的全部素数,必须把不大于 的所有素数的倍数剔除,剩下的就是素数。
    • 给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去…。

    如果想知道第N位素数需要从多少个自然数中找,那么还需要根据素数定理,在素数定理中可以给出第n个素数p(n)的渐近估计:在这里插入图片描述 。它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个,它是素数的概率大约是在这里插入图片描述

    代码大概的方法是申请一个布尔类型的数组,利用埃氏筛法筛选,当该数组的值是true的时候的们就认为该数不是素数。找出第1百万位素数 运行时间1856毫秒约等于2秒钟。

    代码如下图:
    在这里插入图片描述

    展开全文
  • 一、算法原理 一个合数总是可以分解成若干个质数的乘积,那么如果把质数(最初只知道2是质数)的倍数都去掉,那么剩下的就是质数了。 二、步骤 (1)先把1删除(1既不是质数也不是合数) (2)读取队列中当前...

    一、算法原理


    一个合数总是可以分解成若干个质数的乘积,那么如果把质数(最初只知道2是质数)的倍数都去掉,那么剩下的就是质数了。


    二、步骤


    (1)先把1删除(1既不是质数也不是合数)

    (2)读取队列中当前最小的数2,然后把2的倍数删去

    (3)读取队列中当前最小的数3,然后把3的倍数删去

    (4)读取队列中当前最小的数5,然后把5的倍数删去

    .......

    (n)读取队列中当前最小的状态为true的数n,然后把n的倍数删去





    三、实现


    问题:给一个数n,求出比n小的所有的质数有多少个


    思路:用一个bool数组,存储n个数的状态,初始化都为true,然后从2开始,如果2的状态为true,就开始遍历比n小的所有的2的倍数,将其全部置为false。把2的倍数遍历完后,继续往下找下一个状态为true的数,即3,遍历比n小的所有的3的倍数(按3*3,3*4,3*5这样遍历,注意不需要从3*2开始了)。.....最后剩下的状态为true的数全为质数。


    四、代码

    class Solution {
    public:
        int countPrimes(int n) {
            if(n<=1)  //小于等于1的都不是质数
                return 0;
            bool* a = new bool[n+1];
            for(int i=0; i<n; i++)
                a[i] = true;
            for(int i=2; i*i<n; i++){
                if(a[i] == true){
                  for(int j=i; i*j<n; j++){
                      a[i*j] = false;
                  }  
                }//if
            }//for
            int result =0;
            for(int i=2; i<n; i++){
                if(a[i])
                    result++;
            }//for
            return result;
        }
    };


    展开全文
  • 由于一个合数总是可以分解成若干个质数的乘积,那么如果把质数(最初只知道2是质数)的倍数都去掉,那么剩下的就是质数了。 例如要查找100以内的质数,首先2是质数,把2的倍数去掉;此时3没有被去掉,可认为是质数...
  • 筛选法找素数算法的一点改进

    千次阅读 2006-12-18 21:58:00
     自从接触编程以来,发现,选找素数这一题目一直是算法界一个长盛不衰的题目,而筛选法似乎是这一题目巧妙极致的一个解法。不过不知足的我们依然不肯罢休,对程序中那几次重复运算始终耿耿于怀。什么时候电脑才能像...
  • 找素数质数算法

    千次阅读 2011-05-12 14:01:00
    在网上看到很多找质数算法,都是检查从2到n-1的数能否被n整除,能就不是质数,反之就是素数,这样做当然是正确的,但是浪费了一些没有必要的检查,其实只要检查从2到sqrt(n)之间的数就可以了,因为如果一...
  • 素数算法

    2020-12-22 16:14:10
    素数算法 package com.jmmq.load.jim.algorithm; /** * 是否是素数算法 * 如果n不是素数, 则n有一个因子d满足1< d <=sqrt(n) * 素数又叫质数质数是指在大于1的自然数中,除了1和它本身以外,不能被其他...
  • 素数算法素数代码

    2011-12-22 13:00:22
    素数算法素数代码
  • 质数算法

    2015-07-27 10:44:52
    15.7.27 质数算法基础
  • voidsushu_filter(longcount){ sz[1]=0; for(longi=2;i<=sqrt(count);i++) { if(sz[i]==1) { for(intj=i*2;j<=count;j+=i) { sz[j]=0; } ...
  • 质数算法之四

    2017-03-19 11:35:53
    public class Eratosthenes算法 { public static void main(String[] args) { int n = 27; int[] primes= new int[n+1]; for (int k = 2; k if (primes[k]==0) { for (int i = k; i System.out....
  • 大范围素数算法

    2014-11-26 23:12:52
    大范围的素数算法,解决素数算法的问题,当程序需要,为什么非得20个字的描述呢
  • 判断素数算法

    2014-09-05 20:34:51
    素数的测试方法,但不完全,算法导论书上的算法
  • 质数算法之一

    2017-03-19 11:20:11
    public class 第一版 { public static void main(String[] args) { int count = 0;//计数变量 int number = 2;...System.out.println("一共有"+count+"个素数"); } }
  • 质数算法之三

    2017-03-19 11:32:19
    import java.util.*; public class 第三版 { public static void main(String[] ...//变量shu是箱子中的一个素数 ...//把素数装到list里面 ...System.out.println("一共有"+count+"个素数"); } }
  • 经典算法2(素数算法).c
  • 数论——素数算法

    2015-10-24 21:53:16
    素数,也叫质数素数算法在解决实际问题乃至ACM竞赛中经常能够用到,在笔者研究这个问题之前,对素数算法的理解仅能达到从1到sqrt(n)除n判断是否是素数的水平。 然而研究素数算法后发现,素数算法可说博大精深,有...
  • 探讨不同的素数求法!从简单的素数解法入手,逐渐深入,并结合计算机的特点得到一个较为合适的素数解法!适合参加ACM竞赛的同学学习!
  • 质数素数算法,及算法优化

    千次阅读 多人点赞 2019-08-11 10:47:29
    质数素数):只能被1和其本身整除的数字(其中1和0不属于质数) 接下来我们用多种方法求1000以内(包含1000)的质数数量,并且统计每种方法的循环次数 (如果只想知道速度快的方法可以直接看方法五) 方法一: 循环...
  • 相邻素数算法是算法设计与分析的课程里其中一个较为重要的算法
  • 除了数字111和这个数本身,没有其他约数的数,就是质数。另外规定1不是质数,而2是。 关于这个1不是素数的规定,就是质因数分解时,可以有唯一的一种写法,这也是如下定理规定的 将正整数分解成多个素数乘积的方法...
  • C/C++ 出最大素数 算法

    千次阅读 2020-06-04 22:14:45
    24.【中学】出最大素数 小明在中学学习了什么是素数素数是指一个只能被1和它本身整除的数,在数论中占有重要的研究地位,在当代密码学中也被广泛应用。 输入: 取值范围 输出: 该范围内的最大素数 #include ...
  • python求素数算法There are various methods through which we can calculate prime numbers upto n. 我们可以通过多种方法来计算最大为n的素数 。 1) General Method 1)一般方法 In this method, we usually ...
  • 算法素数(质数)判断方法

    万次阅读 多人点赞 2017-11-29 17:05:32
    素数(质数)的判断在算法问题中经常遇到,这里小结几种常用的判断方法。首先,我们来看一下素数(质数)的定义:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。...
  • c代码-求素数算法

    2021-07-16 14:36:52
    c代码-求素数算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,685
精华内容 29,474
关键字:

找质数算法