精华内容
下载资源
问答
  • 埃拉托色尼的经典素数计算方法
    千次阅读
    2013-11-20 23:52:39

    看到埃拉托色尼的经典素数计算方法:

    第一步,列出如下这样以2开头的序列:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

    第二步,标出序列中的第一个素数,主序列变成:(其实什么都没变,我们知道第一个素数是2)

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

    第三步,将剩下的序列中,第二项开始每隔一项划掉(2的倍数,用红色标出),主序列变成:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

    第四步,如果现在剩下的序列中,最大数小于第一个素数的平方,那么剩下的序列全部是素数,否则返回第二步。本例中,因为25大于2的平方,我们返回第二步:

             剩下的序列中第一个素数是3 (大概前面2已经被认定为素数了,不记在其中), 接下来划出3的倍数。

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

             然后再比较3的平方跟25的大小。然后再确定5,再划出5的倍数。一直做下去。

    在本例子中,5的平方等于25了,所以跳出循环,否则继续划出7的倍数,11的倍数,一直做下去。

     

    综上所述,就是在一个序列中,一次划出2,3,5,7……,等素数的倍数,直到整个序列全部都是素数,什么时候停止,即某个素数的平方等于最后一个数。

     

    C程序实现,在这里利用一个数组来表示,该位置1表示素数,0表示合数。

     

    #define N 10000

    main()

    {

             int i ,j,a[N];

             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++) a[j*i]=0;

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

                if(a[i]) printf("M",i);

     

    }

     

    更多相关内容
  • 本文实例讲述了C++回文数及素数问题计算方法。分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 编制一个返回值为bool型的函数isPrimer()...
  • java 素数计算方法

    2014-09-23 16:43:06
    今天花了一整天的时间在研究java中素数计算方法,终于给彻底弄懂了!首先,先看看我上午写的错误代码 public static void main(String[] args){ for(int i=101;i;i++){ for(int j=2;j 当时真是糊涂了,脑子...

                   

                   今天花了一整天的时间在研究java中素数计算的方法,终于给彻底弄懂了!首先,先看看我上午写的错误代码

    	public static void main(String[] args){
    		for(int i=101;i<=200;i++){
    			for(int j=2;j<i/2;j++){
    				if(i%j==0)
    					break;
    				else
    					System.out.println(i);	
    			}
    		}
    	}
    }

     

    当时真是糊涂了,脑子里的思路就是,素数,就是看这个数除以2一直到这个数的一半(开方更准确,我习惯直接除2了),如果都不能整除,则这个数就是素数,抱着这个思路,就写出了if。。。else。。。其实,错也就错在这了。

    if语句判定不是素数,跳出循环,可以!但如果一个数刚开始不能被2 整除,就直接执行else语句判定它是素数,太武断了!(101到200这几个数很巧,我这个程序凑巧判断出来了)而且,我的结果输出一个数好几次,因为else在内层循环里,一直执行。

    研究这个错误研究半天,知道错那了,可也不会写这个题了,参考网上的代码 ,结果发现,好多作者犯了和我一样的错误,挑一个典型说一下:

     

    import java.io.*;
    class sa {
        public static void main(String []args) throws  IOException {
          int i,j;
          String a;
         BufferedReader str=new BufferedReader(new InputStreamReader(System.in));
         System.out.println("请输入一个数");
         a=str.readLine();
         int b=Integer.parseInt(a);
         if (b==2) { 
        	 System.out.println("是质数"); 
        	 return; 
        	 }
            double  sqr=Math.sqrt(b);
            long tt=Math.round(sqr);
            for(i=2;i<=tt;i++) {
                if (b%i==0){
                System.out.println("不是质数");
               break;
                  }else {
                 System.out.println("是质数");
              break; 
        } 
          }
     }
    

    先不说代码很复杂了,输入105,显示105是质数!犯了和我一样的错误!具体就不说了。看到一位作者的正确的代码,思路很奇妙:    

     

     

    public class qisi {
    	public static void main(String[] args) {
    	int sum = 0;
    	for (int i = 101; i <= 200; i++){
    	for (int j = 2; j <= i; j++) {
    	if (i % j == 0 && i == j) {
    	sum++;
    	System.out.println(i);
    	} else if (i % j == 0 && i != j)
    	break;
    	}
    	}
    	System.out.println("101-200 之间有:"+sum+"个素数");
    }
    }

     


    理解了作者的结题思路。感觉自己应该想不到,就又研究了一种思路

     

     

     

    public class sushu {
    	public static void main(String[] args){
    		for(int i = 101;i<200;i++){
    			int n=0;
    			for(int j=2;j<=i/2;j++){
    				if(i%j==0)
    				n=n+1;
    				}
    			if(n==0)
    				System.out.println(i);
    		}
    		}
    	}

    就是内层for循环与外层for循环之间定义一个变量n,在内层for循环中,如果i%j等于0.n自增,最后判断n的值,如果n等于0,就说明i是素数,相比之下,感觉自己的算法,更简单点。

     

    判断素数的方法还有很多,今天我算是学到了,也知道for循环魅力无穷,但稍不留神,就一错千里了!

     

    展开全文
  • 【数论】求素数的三种方法

    千次阅读 2021-10-26 12:44:51
    素数的三种方法:试除法、埃氏筛法、欧拉筛法

    素数的定义

    素数也叫质数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做素数;否则称为合数(规定1既不是质数也不是合数)。

    一、试除法(判断素数)

    试除法顾名思义就是用 2 到 n - 1 的数一个一个试除,如果 n 不能整除这之间所有的数,那么说明它就是素数。这样从 2 试到 n - 1,显然时间复杂度是O(n)的,那么有没有方法可以降低时间复杂度呢?答案是肯定有的,可以证明这个循环范围可以缩小到从 2 到 \sqrt{n},那么时间复杂度就缩短到了O(\sqrt{n})

    再对循环式子进行稍微的变形,C++代码如下:

    bool is_prime(int n)
    {
        if(n < 2) return false;
        for(int i = 2; i <= n / i; i++)   // 这里用 i <= n / i 或 i * i <= n 比 i <= sqrt(n)要好
            if(n % i == 0)
                return false;
        return true;
    }

    二、埃氏筛法(求一个范围中的所有素数)

    试除法的弊端非常明显,如果要求一个范围中的所有素数,用试除法一个一个判断效率就太低了。

    埃氏筛法是用于解决这类问题的古老而简单高效的方法,可以快速找到[2, n]中的所有素数。

    具体操作是这样的:从2开始寻找素数,每次找到一个素数后就将它的倍数全部筛掉,并将该素数存储到另一个队列(数组)中,不断循环,直至原队列(数组)为空。

    时间复杂度为O(n\,log\,logn)

    C++代码如下:

    int primes[N], cnt;   // primes[]存储所有素数
    bool st[N];   // st[x]存储x是否被筛掉
    
    void E_sieve(int n){
        for(int i = 2; i <= n / i; i++){
            if(!st[i]){
                primes[cnt++] = i;
                for(int j = 2 * i; j <= n; j += i)   // 这里可以优化成 int j = i * i
                    st[j] = true;
            }
        }
    }

    三、欧拉筛法(埃氏筛法的优化版)

    埃氏筛法中,由于一个数可以既是一个素数的倍数,又是另一个素数的倍数,可以发现这会出现重复标记的情况,即同一个数被筛掉了不止一次,浪费操作了。

    欧拉筛法就是在埃氏算法的基础上多了判断的步骤,从而消去了这种重复标记的情况,核心思路是用合数中的一个因数筛掉这个合数。

    具体操作为:利用已经求得的素数,第一重循环将区间内的数从小到大遍历,第二重循环将已求得的素数从小到大遍历,将这个数和素数的乘积标记为合数。如果一个数能被素数整除,跳出循环。

    时间复杂度为O(n)

    C++代码如下:

    int primes[N], cnt;   // primes[]存储所有素数
    bool st[N];   // st[x]存储x是否被筛掉
    
    void Euler_seive(int n){
        for(int i = 2; i <= n; i++){
            if(!st[i]) primes[cnt++] = i;
            for(int j = 0; primes[j] <= n / i; j++){
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;   // 如果这个数能被素数整除,跳出循环
            }
        }
    }

    展开全文
  • matlab开发-查找素数方法。目的是提出一种提供质数的算法
  • 主要介绍了使用Python判断质数(素数)的简单方法讲解,经常被用来做科学计算的Python处理这种小问题当然手到擒来^_-需要的朋友可以参考下
  • 素数的算法

    2019-11-22 18:28:30
    素数 质数又称素数。指整数在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。假设一个数字n,现判断其是否为素数。 1.根据定义当 n ...

    素数

    质数又称素数。指整数在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。假设一个数字n,现判断其是否为素数。
    1.根据定义当 n 只能被 1 和 n 整除的时候他就是素数,换句话说就是 n 不能被 2~n-1 之间的数字整除。

    import java.util.Scanner;
    public class Test{
        public static boolean isPrime1(int n) {
            for (int i = 2; i < n ; i++) {//计算从2~n-1中是否存在数字可以被n整除 
                if(n % i == 0) {
                    return false;
                }
            }
            return true;
        }
        public static void main(String[] args){
        	Scanner sc = new Scannr(System.in);
        	System.out.println("请输入一个数字 :");
        	int n = sc.next.Int();
        	System.out.println(isPrime1(n));//打印函数的返回值
        }
    }    

    2.为了简化计算过程我们想到了另外一个办法:
    任意一个数字n都可以写成: n = ab—>例如说:8
    8 = 1
    8, 8 = 2*4 其中 1,2,4,8 都为 8 的因数 ,在他的除 1 与 8 的因数中必定存在一个数字小于 8/2,所以当 2 ~ n/2 中出现了可以被 n 整除的数字则 n 就不是素数。

    import java.util.Scanner;
    public class Test{
        public static boolean isPrime2(int n) {
            for (int i = 2; i <= n/2 ; i++) {//计算从2~n/2是否存在数字可以被n整除
                if(n % i == 0) {
                    return false;
                }
     ==       }
            return true;
        }
        public static void main(String[] args){
         Scanner sc = new Scannr(System.in);
         System.out.println("请输入一个数字 :");
         int n = sc.next.Int();
         System.out.println(isPrime1(n));//打印函数的返回值
        }
    }   

    3.在2的基础之上我们有延伸出了一种办法:
    任意一个数字n都可以写成:n = ab—>例如说:8
    8 = 1
    8, 8 = 2*4 其中 1,2,4,8 都为 8 的因数 ,在他的除 1 与 8 的因数中必定存在一个数字小于根号8,所以当 2 ~ 根号8 中出现了可以被 n 整除的数字则 n 就不是素数.

    
    import java.util.Scanner;
    public class Test{
        public static boolean isPrime(int n) {
            for (int i = 2; i <= Math.sqrt(n) ; i++) {//在Java中 Math.sqrt(n)求开根号,计算从2~根号8间
                if(n % i == 0) {                      //是否存在数字可以被n整除
                    return false;
                }
            }
            return true;
        }
        public static void main(String[] args){
         Scanner sc = new Scannr(System.in);
         System.out.println("请输入一个数字 :");
         int n = sc.next.Int();
         System.out.println(isPrime1(n));//打印函数的返回值
        }
    }  

    ===================
    以上为简单算素数的办法

    展开全文
  • 素数求解的的几种简单方法

    万次阅读 多人点赞 2018-04-22 10:16:40
    问题:打印出100到200之间的素数方法一:素数N就是除了1和它本身之外没有任何因子的数,所以要求素数我们很容易想到从2到N-1去试除,如果能除尽说明它不是素数,这个时候就接着判断下一个数也就是下面的这种 上结果...
  • 如果你也正在学习关于此类的题目可以仔细阅读这篇文章,了解一下循环结构、素数的基本语法知识。 题目: 7-5就区间正整数内所有素数之和 (20分) 【描述】求m-n以内所有素数之和并输出。‬‮‬‪‬‮‬‪‬‪‬‪‬...
  • 程序分析:判断素数方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 代码如下:#include <stdio>#include <math.h> void main(){ int low,high,t=0; printf(“请...
  • 暴力法 | 暴力法优化(取中间数)|暴力法优化(取平方根)|埃氏筛法|未知算法。五种算法的效率依次递增。在同一个Prime.java文件中都可以测试。
  • MATLAB之素数的五种计算方法

    万次阅读 多人点赞 2019-05-19 19:40:57
    使用MATLAB实现求素数方法大同小异,这是在自己做作业时整理的几种,有用的话可以看一下! NUM.1 y = []; for i = 1:1:1000; for j = 2:1:i-1 if (mod(i,j)==0) break;%以此判断该数字是否可以被前面的数字...
  • (初学者)素数计算

    千次阅读 2017-03-29 09:15:11
    前言记得我刚开始学习OI的时候接触到的最早的算法莫过于素数算法。当然了,素数这个知识小学的时候我们就已经有所学习了。当时我一直有一个疯狂的设想,就是编写一个程序把我能算出来的素数都算出来。
  • 如何计算素数

    千次阅读 2018-11-20 13:47:17
    题目:如何计算素数? 思路:素数只可以被1和它本身相除,所以我打算把素数从2除到它减去1 解答: for i in range(100,201): for j in range(2,i-1): if(i%j==0): break else: print("%d "%i,...
  • 方法一,用for循环来实现 num=[]; i=2 for i in range(2,100): j=2 for j in range(2,i): if(i%j==0): break else: num.append(i) print(num) 方法二,用函数来实现 import math def func_get_prime(n): ...
  • java素数(质数)计算

    千次阅读 2020-10-16 17:57:11
    素数的定义: ...//素数(质数)计算方法 public static void main(String[] args) { int icount = 0; for (int i = 2; i <= 1000; i++) { for (int j = 1; j <= i; j++) { if (i % j == 0)
  • PHP 素数计算算法示例

    2021-03-24 08:33:06
    摘要 腾兴网为您分享:PHP 素数计算算法示例,影视大全,小学英语,上海交通,奇秀直播等软件知识,以及大同证券v6,控制时间,网购,日月凌空,分享,抢票大师,天津市专业技术人员继续教育网,绝地求生1450,品职...
  • 编写程序:计算100-10000之间有多少个素数,并输出所有素数
  • 一种寻找大素数的简易方法,张胜持,,本文提出了一种简单易行的寻找大素数方法,以z=43+60n的公式来进行计算,n可以趋近于无穷大,因而计算出来的大素数z也趋近于无穷�
  • Python素数检测的方法

    2021-02-04 09:06:37
    本文实例讲述了Python素数检测的方法。分享给大家供大家参考。具体如下:因子检测:检测因子,时间复杂度O(n^(1/2))def is_prime(n):if n < 2:return Falsefor i in xrange(2, int(n**0.5+1)):if n%i == 0:return...
  • 素数,就是除了1和本身以外没有除后余为零的数,如 1, 3,5等 int i = 0; int j = 0; for(i=100; i&amp;lt;=200; i++) { int count = 0; for(j=2; j&amp;lt;i; j++) { if(i%j == 0) ...
  • 计算整数区间[2,n]中所有素数的最为简便的筛法——埃氏筛法。 设u[]为筛子,初始区间中的所有数在筛子u[]中。按递增顺序搜索u[]中的最小数,将其倍数从u[]中筛去,最终留下的数即为素数。 int i,j,k; f...
  • C++高效计算素数方法

    千次阅读 2017-12-17 12:39:28
    在网上看到很多计算素数的c++例子,本人试了一下觉得效率不高,于是字自己写了个算,效率还算可以,如图! 我们要计算素数,首先要明确素数定义及性质: 分析题目理清思路 又称质数,有无限个。质数定义为在大于1的...
  • 如果输入的数字不符合规范,则给出提示,并不予以计算。如果是素数则提示“是素数”,如果不是素数,则给出提示“不是素数”,并且给出不是素数的理由,例如9不是素数,因为9=3*3。本资源是VB源码。
  • 使用米勒检验的素数计算程序 该程序建立在Miller测试概念的基础上,并使用完全无偏差的方法来提供质数通过测试的准确概率,有效的素数测试受Python解释器速度慢以及缺少多核处理和多线程的限制我可能会补充一点。 ...
  • 判断素数的 5 种方法

    千次阅读 2020-02-13 10:49:56
    判断素数的 5 种方法 方法 1 ​ 从 2 到 x-1 是否可以整除。能:不是素数;不能:是素数。特别的,1 不是素数 /** 输入:x:需要判断的数 输出:0:不是素数;1:是素数 **/ int isprime(int x) { int ret=1; int ...
  • 素数又叫质数,质数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。 问题: 输入一个整数n,输出1~n中的素数,里有详细解释,有问题也欢迎留言!谢谢支持啦~
  • Java计算素数

    万次阅读 2017-07-29 12:04:29
    1 什么是素数素数又称质数,指的是,除了1和它本身,没有第...2 如何计算根据质数(素数)的定义不难得出,要计算一个数是不是质数,需要明确是不是除了1和本身以外,还有其他除数。由此可以有一个计算思路: 给定一个

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,210
精华内容 16,884
关键字:

素数计算方法

友情链接: rs232.zip