VR全景图片 反射 unix deployment drupal mtu原理 Skeljs bootstrap后台管理模板 数据库设计规范 matlab 图像识别 string转16进制 android入门实例 lora开发 linux撤销 excel带格式复制粘贴 python正则 python逻辑运算符 python操作mongodb python加注释 python变量定义 python读文件 python免费教程 python安装程序 java编程课程 java写入文件 java获取当前时间 subprocess 网络电视软件下载 不寻常的指南针 易语言进度条 删除数组中的某个元素 福昕阅读器绿色版 god2iso win10画图 iframe跨域 火萤壁纸下载 免费微信答题制作 脚本学习 win98序列号 autocad2004迷你版
当前位置: 首页 > 学习教程  > 编程语言

判断一个数是否是素数的 n 多种方法

2020/11/4 14:05:30 文章标签:

素数:只能除以1和自身的数(需要大于1)就是素数,又叫质数。 方法 从2开始一直除到该数之前的那个自然数,如果有能被整除的就不是素数 bool isPrime(int n) {if (n 1) {return false;}if (n 2) {return true;}for (…

        素数:只能除以1和自身的数(需要大于1)就是素数,又叫质数。

方法

  1. 从2开始一直除到该数之前的那个自然数,如果有能被整除的就不是素数
bool isPrime(int n) {
	if (n == 1) {
		return false;
	}
	if (n == 2) {
		return true;
	}
	for (int i = 2; i <n ; ++i) {
		if (n % i== 0) {
			return false;
		}
	}
	return true;
}

       

  1. 假设 d 为 n 的约数,那么 n/d 也是 n 的约数,因为有: n = d * (n/d),即:min(d, n/d) <= sqrt(n),因此我们只要检测 2 ~ sqrt(n) 范围内所有的整数就可以了,
bool isPrime(int n) {
	if (n == 1) {
		return false;
	}
	if (n == 2) {
		return true;
	}
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i== 0) {
			return false;
		}
	}
	return true;
}

       

  1. 如果不能被 2 整除,那么 n 即为奇数,判断其是否能被奇数整除就好了,因此循环的范围就可以减小为 [3, sqrt(n)]内的奇数
bool isPrime(int n) {	
	if (n == 2) {                               // 2 是素数
		return true;
	}
	if (n != 2 && n % 2 == 0) {             	// 如果能被 2 整除,证明 n 不是素数(2 本身除外) 
		return false;
	}
	// 如果不能被 2 整除,那么 n 即为奇数,判断其是否能被奇数整除,前面我们已经处理了 2 和 2 的倍数,因此这个循环的范围就是 [3, sqrt(n)]内的奇数
	for (int i = 3; i <= sqrt(n); i += 2) {     //i <= sqrt(n); 可以换成i*i<n。为什么加2,因为能被偶数整除的,一定能被2整除。上面已经讨论过了
		if (n % i == 0) {
			return false;
		}
	}
}

        上面的其实是之前我写过的,用的c++,回文字符串判断、素数的判断、求最大公约数最小公倍数(c++)我懒得改了,下面的会用一些 python 的

       

  1. 既然可以通过除以 2 这个素数来先排除一半 ,那么我已可以除以其他的3、5、7、11来再排除一些嘛
def isPrime(n):
    if n <= 1:
        return False
    elif n % 2 == 0 and n != 2:     # 去除能被2整除的  不包括2
        return False
    elif n % 3 == 0 and n != 3:     # 去除能被3整除的  不包括3
        return False
    elif n % 5 == 0 and n != 5:     # 去除能被5整除的  不包括5
        return False
    elif n % 7 == 0 and n != 7:     # 去除能被7整除的  不包括7
        return False
    else:
        for i in range(3, int(math.sqrt(n)) + 1, 2):   # 这里 +1是因为range不含end值,是个左闭右开的(start,end)
                if n % i == 0:
                    return False
        return True

       

  1. 所有的素数都在6的倍数的左侧或者右侧,也即num % 6 == 1 || num % 6 == 5,不满足者不是素数,满足者继续验证,步骤如下
  • 对于1,2,3三个数字特殊处理
  • 所有的素数都在6的倍数的左侧或者右侧,也即num % 6 == 1 || num % 6 == 5,不满足者不是素数,满足者继续验证
  • 计算sqrt(num),从5,11,17,23…开始验证,每次验证i和i+2,一旦整除,不是素数多次筛的时候可以打表。
           
            注意: 只有6的倍数附近的数才有可能是质数。为什么说可能是质数的,我举个反例,25,35,49。。。
bool isPrime(int n) {
    if (n == 2 || n == 3) {            // 先排除2、3这两个特例 
        return true;
    }
    if (n % 6 != 1 && n % 6 != 5) {    //如果不在6的倍数附近,肯定不是素数
        return false;
    } 
    for (int i = 5; i <= sqrt(n); i += 6) {   //对6倍数附近的数进行判断
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

       

  1. 费马素性检验,基于费马小定理。缺点:在 232以内,这种方法的准确性尚可接受,但到了 264级别,出错的概率就太高了。

费马小定理wiki

假如a是一个整数,p是一个质数,那么 ap - a 是p 的倍数
       
那么反过来呢?如果存在某个 ap - a 是p 的倍数,是否就能判定 p 是素数呢?并不行,
       
例如 2341 - 2 是341 的倍数,但 341 是合数;再比如 31105 - 3 是 1105的倍数,但 1105 是合数;这类合数被称为费马伪素数。
       
不过幸好,一个合数是费马伪素数的概率并不是很高。所以我们可以多测试几个 a,只要有一个a不满足,就说明即可说明 p 不是素数。
       
都成立,那它就很可能是素数了。注意,是很可能,不是一定是

import random
def isprime(n,k=128):   // 默认测试128 个a
    if n<2:
        return False
    for _ in range(k):
        a = random.randrange(1,n)
        if pow(a,n-1,n)!=1:
            return False
    return True

        这个东西我也不是很熟啊,所以建议配合Wiki看,Wiki比我讲的好的多

       

  1. 米勒-罗宾(Miller-Robin)素性检验。解决了费马素性检验错误率有点高的情况,

在这里插入图片描述
       

#include <iostream>
using namespace std;

typedef long long ll;

ll qpow(ll a, ll n, ll p)      // 快速幂
{
    ll ans = 1;
    while (n){
        if (n & 1)
            ans = (__int128)ans * a % p;      // 注意!中间结果可能溢出,需要使用__int128过渡
        a = (__int128)a * a % p;
        n >>= 1;
    }
    return ans;
}

bool is_prime(ll x)
{
    if (x < 3)                 // 特判1,2
        return x == 2;
    if (x % 2 == 0)            // 特判偶数
        return false;
    ll A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
    while (d % 2 == 0)         // 算出d, r 
        d /= 2, ++r;
    for (auto a : A){
        ll v = qpow(a, d, x);        // a^d
        if (v <= 1 || v == x - 1)    // 如果a^d≡0,说明是a是x的倍数;如果a^d≡1或-1,说明这串数接下来一定都是1,不用继续计算
            continue;
        for (int i = 0; i < r; ++i){
            v = (__int128)v * v % x; // 同样使用__int128过渡
            if (v == x - 1){         // 得到-1,说明接下来都是1,可以退出了
                v = 1;
                break;
            }
            
            if (v == 1)              // 在中途而非开头得到1,却没有经过-1,说明存在其他数字y≠-1满足y^2≡1,则x一定不是奇素数
                return false;
        }
        if (v != 1)                  // 查看是不是以1结尾
            return false;
    }
    return true;
}

int main()
{
    cout<<bool(is_prime(6))<<endl;
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_350066.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?