介绍线性筛法用于质数筛选

目录

• 何为质数

  • 如何判定质数

  • • 1.直接判定法
    • 2.改进后的枚举方法

  • 如何筛选素数

  • • 1.埃拉托斯特尼筛法
    • 2.线性筛法
    • • 实施方式
      • 核心原理

质数定义与特性

质数，亦称为素数，指的是在自然数范围内，大于1的数值中，仅能被1和其本身整除的数。若一个数存在除1和自身以外的其他因数，则该数被定义为合数。——百度

质数判定方法解析

1.暴力判断方法分析

通过依次列举i:2\rightarrow n-1的所有数值进行检验，若发现某个i能够整除n，则可判定n为合数；反之，若在全部范围内均未找到能整除n的i，则可确认n为质数。该判断方式完全依据质数与合数的定义进行推理。

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