美文网首页
质数-试除法

质数-试除法

作者: dachengquan | 来源:发表于2020-08-04 20:29 被阅读0次

质数

质数的定义:若一个正整数无法被1和他自身除外的任意自然数整除,则称该数为质数,否则为合数。

0和1不是质数也不是合数
质数的数量:在整个自然数集合中,质数的数量不多,分布比较稀疏,对于一个足够大的整数N,不超过N的质数大约N / \ln N个每\ln N个数中大约有一个质数。

试除法

试除法用于解决质数的判定给出一个数n,判定n是不是质数。
定理:若一个正整数N为合数则存在一个能整除N的数T,其中2 \leq T \leq \sqrt{N}
证明:因为N是合数,所以一定存在一个数M能整除N,并且2 \leq M \leq \sqrt{N}
反证法,假设上面命题不成立,不存在这样的M,那么M一定\sqrt{N}+1 \leq M \leq N-1。因为M能整除N所以N/M也能整除N,并且2 \leq N/M \leq \sqrt{N},令T=N/M存在这样数使得假设不成立,原命题成立。
我们只需要扫描2~\sqrt{n}直接的所有整数,依次检查他们能否整除N,如果都不能N是质数,否则N是合数。

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

相关文章

  • 质数-试除法

    质数 质数的定义:若一个正整数无法被1和他自身除外的任意自然数整除,则称该数为质数,否则为合数。 0和1不是质数也...

  • 数学知识

    一、数论 首先需要掌握质数的定义,判断一个数是否是质数的试除法、Miller–Rabin等。学习筛法,求出1~N之...

  • 质因数分解-试除法

    算数基本定理任何一个大于1的正整数都能被唯一分解为有限个质数的乘积。其中是正整数,是质数,且满足试除法结合质数判定...

  • 质数、约数、欧拉函数基础知识

    不想做题了,那就来总结吧 0X00 质数 判断一个数字是不是质数 可以用试除法 原因是一个数的约数是成队出现的 ...

  • 试除法解决质数问题(Python3)

    浅析求解质数问题的一些方法 质数问题是算法中常见的和入门的问题,今天姑且用 "打印100以内所有质数" 这个问题,...

  • Python---试除法求质数的三种方式对比

    此三种方法都是基于试除法,即不断地尝试能否整除。比如要判断自然数 x 是否质数,就不断尝试小于 x 且大于1的自然...

  • 约数-试除法

    求N的正约数集合-试除法 若d>是一个约数那么也是一个约数。每个约数都是关于对称的。还有完全平方数。因此只要扫描1...

  • 数学日记

    在目前我学到的知识中,有小数除法,轴对称和平移,还有倍数特征,质数。 第一单元学的是小数除法,我们学了小数除以整数...

  • 及时调整教学策略

    内容:北师大版二年级下册一单元除法第4课《分草莓》(试商)。 学习目标:1.结合分草莓的情境,探索有余数除法的试商...

  • 【华为机试】质数因子

    题目描述: 功能:输入一个正整数,按照从小到大的顺序输出它的所有质数的因子 输入描述: 输入一个long型整数 输...

网友评论

      本文标题:质数-试除法

      本文链接:https://www.haomeiwen.com/subject/pjirrktx.html