精华内容
下载资源
问答
  • 判断是否是质数的快速方法
    千次阅读
    2021-01-20 10:19:33

    算法一:针对输入的数字x,我们可以遍历从2到x-1这个区间中的数,如果x能被这个区间中任意一个数整除,那么它就不是质数。

    def is_prime1(x):
        for i in range(2, x):
            if num % i == 0:
                return False
        return True

    算法二:对算法一的优化,事实上只需要遍历从2到√x即可。

    def is_prime2(x):
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True

    算法三:偶数中除了2都不是质数,且奇数的因数也没有偶数,因此可以进一步优化。

    def is_prime3(x):
        if x == 2:
            return True
        elif x % 2 == 0:
            return False
        for i in range(3, int(x ** 0.5) + 1, 2):
            if x % i == 0:
                return False
        return True

    算法四:任何一个自然数,总可以表示成以下六种形式之一:6n,6n+1,6n+2,6n+3,6n+4,6n+5(n=0,1,2...)我们可以发现,除了2和3,只有形如6n+1和6n+5的数有可能是质数。且形如6n+1和6n+5的数如果不是质数,它们的因数也会含有形如6n+1或者6n+5的数,因此可以得到如下算法:

    def is_prime4(x):
        if (x == 2) or (x == 3):
            return True
        if (x % 6 != 1) and (x % 6 != 5):
            return False
        for i in range(5, int(x ** 0.5) + 1, 6):
            if (x % i == 0) or (x % (i + 2) == 0):
                return False
        return True

    转自:https://zhuanlan.zhihu.com/p/107300262?utm_source=wechat_session 

    更多相关内容
  • 判断素数最快方法

    千次阅读 2021-05-25 09:36:53
    判断素数最快方法 1、普通方法 bool is_prime(int n) { if (n < 2) return false; int i; for (i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 原理是对每个数进行...

    判断素数最快的方法

    1、普通方法

    bool is_prime(int n)
    {
        if (n < 2)
            return false;
        int i;
        for (i = 2; i < n; i++)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    

    原理是对每个数进行开方,模运算。
    我们来统计0~100000之间有多少素数,并计算程序运行的时间。

    int main()
    {
        clock_t start, finish;
        double totaltime;
        start = clock();
        int n = 0;
        for (int i = 0; i < 100000; i++)
        {
            if (is_prime(i))
            {
                n++;
            }
        }
        cout << "n = " << n << endl;
        finish = clock();
        totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
        cout << "\n此程序的运行时间为" << totaltime << "秒!" << endl;
        return 0;
    }
    

    运行结果如下:

    n = 9592
    此程序的运行时间为1.244秒!
    

    平时需求不太大,勉勉强强能接受这个速度吧。
    但是范围增加到0~1000000,

    for (int i = 0; i < 1000000; i++)
    
    n = 78498
    此程序的运行时间为102.255秒!
    

    这个时间太长了。如果数据量再大一点,那我岂不是要等到天荒地老?

    2、目前我发现的最快的方法

    n>3时,对一个数字进行模6运算,如果结果是0,2,3,4,那么这个数肯定不是素数。

    这样就节省了2/3的工作量。

    接下来和第一种方法类似,不过是从5开始,步长为6,
    除数i和i+2都是奇数并且都是质数,这又减少了特别多的工作量。

    bool is_prime(int num)
    {
        if (num <= 3)
            return num > 1;
        if (num % 6 != 1 && num % 6 != 5)
            return false;
        int s = sqrt(num);
        for (int i = 5; i <= s; i += 6)
            if (num % i == 0 || num % (i + 2) == 0)
                return false;
        return true;
    }
    

    现在运行一下0~100000的结果:

    for (int i = 0; i < 100000; i++)
    
    a = 9592
    此程序的运行时间为0.005秒!
    

    0.005秒,跟1.244秒比,速度是原来的248.8倍。

    接下来

    for (int i = 0; i < 1000000; i++)
    
    n = 78498
    此程序的运行时间为0.064秒!
    

    0.064秒相比于102.255秒,速度增加1597.7倍!简直是一个天上一个地下。

    接下来再增大范围:

    for (int i = 0; i < 10000000; i++)
    
    n = 664579
    此程序的运行时间为1.43秒!
    
    for (int i = 0; i < 100000000; i++)
    
    n = 5761455
    此程序的运行时间为36.375秒!
    

    行了行了,到此为止。

    展开全文
  • 判断质数 素数——我知道的最快方法.pdf
  • 判断一个数是否质数素数)的4种方法

    万次阅读 多人点赞 2019-07-20 15:38:30
    2.如何判断是否质数方法1 方法2 方法3 方法4 1.什么是质数? 首先来看质数的概念: 质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。(也可定义...

    目录

    1.什么是质数?

    2.如何判断是否为质数?

    方法1

    方法2

    方法3

    方法4


    1.什么是质数?

    首先来看质数的概念:

    质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。(也可定义为只有1与该数本身两个正因数的数)

     

    图1  数字12不是质数,而数字11是质数

    如上图所示,数字12可以将每4个分成一组,一共3组;而数字11将每4个、每5个、每3个分成一组都无法全部分完,而有剩余,因此将数字11称为质数。

     

    2.如何判断是否为质数?

    质数的特点如下:

    一个自然数(如1、2、3、4、5、6等)若恰有两个正约数(1及此数本身),则称之为质数。

    方法1

    根据质数的约数只有1和本身这一特点,可以首先想到最直观的方法。第一种方法就是判断一个数是否能被比它小的数整除

    方法1的时间复杂度是O(n)。

    public static boolean isPrime(int n){
        //n<=3时,质数有2和3
        if (n <= 3) {
            return n > 1;
        }
        //当n>3时,质数无法被比它小的数整除
        for(int i = 2; i < n; i++){
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    方法2

    当一个数不是质数时,必定存在两个约数,一个大于等于sqrt(n),另一个小于sqrt(n)。利用这种特性,可以对方法1进行改进,只判断数n能否被小于sqrt(n)的数整除。

    方法2的时间复杂度是O(sqrt(n))。

    图2  筛选判断集,只选择小于等于sqrt(n)的集合

     

    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }
        //判断一个数能否被小于sqrt(n)的数整除
        int sqrt = (int)Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

    方法3

    任一偶数一定能分解为2和其他偶数/奇数的积,因此一个数不能被2整除,那么这个数一定不能被其他偶数整除。利用这个特点,可以对方法2进行改进,判断数n能否被小于sqrt(n)的奇数整除。

    方法3的时间复杂度是O(sqrt(n)/2)。

    图3  进一步筛选判断集,只选择小于等于sqrt(n)的奇数
    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }
        //只需判断一个数能否被小于sqrt(n)的奇数整除
        int sqrt = (int)Math.sqrt(n);
        for (int i = 3; i <= sqrt; i += 2) {
            if(n % 2 == 0 || n % i == 0) {
                return false;
            }
        }
        return true;
    }

    方法4

    质数的分布具有特点,经过证明可以得到,(大于等于5的)质数一定和6的倍数相邻,一定是6x-1或6x-1。利用这种特性。可以对整数进行筛选,只判断那些是6x-1或6x-1的整数是否为质数。

    图4  筛选数据集,只选择6的倍数相邻的数

    证明过程如下:

    令x≥1,将大于等于5的自然数表示如下: ······6x-1,6x,6x+1,6x+2,6x+3,6x+4······(相邻6个数为一组)

    在以上的数字中,6x、6x+2和6x+4是偶数,一定不是质数;6x+3可以分解为3(2x+1),不是质数,因此质数只能是6x-1和6x+1。

    public static boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }
        // 只有6x-1和6x+1的数才有可能是质数
        if (n % 6 != 1 && n % 6 != 5) {
            return false;
        }
        // 判断这些数能否被小于sqrt(n)的奇数整除
        int sqrt = (int) Math.sqrt(n);
        for (int i = 5; i <= sqrt; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

     

    展开全文
  • Java判断质数/素数的三种方法

    千次阅读 2022-07-19 00:58:13
    质数在中,如果只包含1和本身这两个约数,就被称为质数素数

    介绍

    质数:在大于1的整数中,如果只包含1和本身这两个约数,就被称为质数(素数)

    解法

    解法一:暴力枚举

    枚举从2 ~ N的每一个数
    实际上不用枚举到N,只需要枚举到√N就行

    注意:

    1. 不要使用sqrt()函数,直接求√n,因为该函数运算较慢
    2. 注意数据溢出,i * i <= n可能会溢出,推荐使用i <= n / i
    public static boolean isPrime(int n) {
           // 枚举到√n,注意溢出
           for(int i = 2; i <= n / i; i++)
               // 如果i可以整除n,说明n不是素数,直接return false
               if(n % i == 0)
                   return false;
           // 说明n是素数
           return true;
    }
    

    解法二:埃氏筛法

    public static boolean isPrime(int n){
        int [] arr = new int[n+1];
        // 1:质数   0:非质数
        Arrays.fill(arr,1);
    
        for(int i = 2; i <= n; i++){
            if(arr[i] == 1){
                // 将i的倍数去除掉
                for(int j = i+i; j <= n; j += i){
                    arr[j] = 0;
                }
            }
        }
        return arr[n] == 1 ? true : false;
    }
    

    解法三:线性筛法

    public static boolean isPrime3(int n){
        // 质数集合
        List<Integer> primes = new ArrayList<>();
        int [] arr = new int[n+1];
        // 1:质数   0:非质数
        Arrays.fill(arr,1);
    
        for(int i = 2; i <= n; i++){
            if(arr[i] == 1)
                primes.add(i); // 添加集合中
            // 筛选,
            for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){
                // 标记
                arr[i*primes.get(j)] = 0;
                // 保证每个合数只会被它的最小质因数筛去,减少冗余
                if(i % primes.get(j) == 0)
                    break;
            }
        }
        return arr[n] == 1 ? true : false;
    }
    

    集合可以换成数组,用一个变量来保存当前集合中的质数数量,相当于下标

    全部代码

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Prime{
    
        public static void main(String[] args) {
            System.out.println(isPrime(430348));
            System.out.println(isPrime2(430348));
            System.out.println(isPrime3(430348));
        }
    
        // 暴力枚举
        public static boolean isPrime(int n) {
            // 防止溢出
            for(int i = 2; i <= n / i; i++)
                if(n % i == 0)
                    return false;
            return true;
        }
    
        // 埃氏筛法
        public static boolean isPrime2(int n){
            int [] arr = new int[n+1];
            // 1:质数   0:非质数
            Arrays.fill(arr,1);
    
            for(int i = 2; i <= n; i++){
                if(arr[i] == 1){
                    // 将i的倍数去除掉
                    for(int j = i+i; j <= n; j += i){
                        arr[j] = 0;
                    }
                }
            }
            return arr[n] == 1 ? true : false;
        }
    
    
        // 线性筛法
        public static boolean isPrime3(int n){
            // 质数集合
            List<Integer> primes = new ArrayList<>();
            int [] arr = new int[n+1];
            // 1:质数   0:非质数
            Arrays.fill(arr,1);
    
            for(int i = 2; i <= n; i++){
                if(arr[i] == 1)
                    primes.add(i); // 添加集合中
                // 筛选,
                for(int j = 0; j < primes.size() && primes.get(j) <= n / i; j++){
                    // 标记
                    arr[i*primes.get(j)] = 0;
                    // 保证每个合数只会被它的最小质因数筛去,减少冗余
                    if(i % primes.get(j) == 0)
                        break;
                }
            }
            return arr[n] == 1 ? true : false;
        }
    }
    
    

    运行截图
    在这里插入图片描述

    展开全文
  • 判断质数/素数——我知道的最快方法

    万次阅读 多人点赞 2017-12-01 20:23:32
    标准版:大部分人都知道的比较方法判断从2到sqrt(n)是否存在其约数,时间复杂度O(sqrt(n)) 高配版:判断2之后,就可以判断从3到sqrt(n)之间的奇数了,无需再判断之间的偶数,时间复杂度O(sqrt(n)/2) 尊享...
  • Python快速判断素数方法

    千次阅读 2021-12-19 22:47:34
    代码 不废话,上代码: ... # 不在 6 的倍数两侧的不是素数 if n % 6 != 1 and n % 6 != 5: return False # 在 6 的倍数两侧的不一定是素数 for i in range(5, int(n ** 0.5) + 1, 6): # i 的步长可以放大到 6
  • C/C++判断是否素数(最快)

    千次阅读 2021-11-22 21:29:07
    质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除...来表示,因为加括号的数肯定为素数,所以只需要判断6n+1和6n+5是否素数,以及最初的1,2,3 #include <iostream> #include <mat.
  • 前言今天看到一个题目,让判断一个数字是否质数.看上去好像不难.因此,我决定实现一下.DOM结构计算500以内的质数并输出$(function(){$("#submit").on('click',function(){var num = $("#num").val();if (isPrimeNum...
  • 计算机或者相关专业,基本上大一新生开始学编程都会接触的一个问题就是判断质数,下面分享几个判断方法,从普通到高效。1)直观判断法直观的方法,根据定义,因为质数除了1和本身之外没有其他约数,所以判断n是否...
  • 【算法】素数(质数)判断方法

    万次阅读 多人点赞 2017-11-29 17:05:32
    素数(质数)的判断在算法问题中经常遇到,这里小结几种常用的...我们可以从它的定义得到判断素数的 第一个方法: 从2到n - 1, 判断是否存在能被n整除的数,既(n%i == 0, 2 ),如果有就不是素数,否则为素数。(这里为了比
  • 质数素数): ...//判断src是不是质数,是返回true,不是返回false private static boolean isPrime(int x) { if(x<=1){ return false; } for (int i = 2; i < x; i++) { if (x%i==0){
  • 判断素数比较方法

    千次阅读 2017-03-06 20:21:55
    public class a{ public static boolean a( int n){ for(int i=2;i if(n%i==0){ return false;  } return true; } } }
  • 传送门 洛谷p3383代码 例题洛谷p3383。 需要特判1不是素数
  • 写一个函数判断一个数是否素数(常规法) #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int a; int i = 0; printf("请输入一个整数:\n"); scanf("%d", &a); for ( i = 2; i &...
  • 素数快速判断方法

    千次阅读 多人点赞 2019-05-25 12:30:38
    原理:大于等于5的素数与6的倍数相邻 证明 所有自然数可以用集合A = { 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 }表示,其中 n >= 0,显然,子集B = {6n, 6n+2, 6n+3, 6n+4}内的元素都不是素数,所以只有6n+1和6n+5可能...
  • 朴素的方法判断从2到sqrt(n)是否有数可以与其整除。(课本都有) 下面介绍一个更方法质数有一个分布规律——大于等于5的质数一定和6的倍数相邻。栗子:5和7,11和13。 由此进行剪枝,达到优化的效果。 Code #...
  • 导入——素数的定义 ...因为质数除了1和本身之外没有其他因数,所以判断n是否质数,根据定义,直接从2到n-1逐个判断是否存在因数可以将n整除即可。 //c++代码 int n; cin>>n; for(int i=...
  • 原文链接:https://www.tandemseven.com/blog/performance-java-vs-node/如果你打开浏览器,搜索“Java与Node.js哪个...在这种情况下,为什么这么多人还是声称Node.js要比Java呢?小编现在就跟大家一起往下看。实...
  • 费马小定理:假如p是质数,a是整数,且a、p互质,那么a的(p-1)次方除以p的余数恒等于1,即:a^(p-1)≡1(mod p)。3.米勒拉宾素性检验法。二次探测定理:如果p是一个素数,04.综合法。试除法+米勒拉宾素性检验。5.AKS...
  • 【第05天】给定一个整数 n 判断是否素数 | 质数的判定与筛选
  • 判断素数方法(java)

    千次阅读 2022-07-09 11:08:00
    判断素数的两种常用方法
  • 在算法竞赛中,我们时常会遇到需要判断一个数是否质数的问题。我们常常利用筛法来解决这个问题,但是当需要判断的数变得很大时,筛法已经无法满足我们的需求。于是我们采用了一个新的方法:**Miller-Rabin素数检测...
  • (理解此算法前应先明白使用 sqrt(num) 为判断条件判断素数方法) 此算法产生的原因(定理):凡是大于5的素数一定与6的倍数相邻 相关证明过程可以去文章末尾的参考博客中查看 由定理可以直接写出算法: #...
  • 【C】C语言判断是否质数

    千次阅读 2022-04-29 22:24:47
    循序渐进逐步优化的写出判断质数的代码。
  • Java 判断一个整数是否质数

    千次阅读 2021-07-13 19:37:42
    Java 使用三元表达式判断一个整数是素数还是合数 import java.util.Scanner; // 导入获取控制台的相关模块 public class PrimeNum { public static void main(String[] args){ // int i = 7; boolean isPrime = ...
  • 分为打表法和单个判断法两类方法 打表法是开始时将所有素数标记出来,适合多次调用判断,前两种属于打表法 单个判断法则是只一个数一个数判断,适合少量判断来节省时间,后俩种属于单个判断法...
  • 算法可以快速计算出我们所需要的结果,例如判断质数,这是很基础的内容,具体如何操作呢?下面小编向大家演示在python如何判断数字是否为质数。质数:一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,654
精华内容 9,461
热门标签
关键字:

判断是否是质数的快速方法