判断素数|质数方法时间效率:线性筛法>埃氏筛法>试除法

在写算法题的时候，各种各样跟素数有关的题目非常常见，本文列出了三种常见的判断素数的方法

三种求素数方法的优缺点

一、试除法

试除法的基本思想是：判断一个数 x 是否为素数，需要检查从 2 到 sqrt(x)（即 x/i）之间的所有数。如果存在一个数 i 能整除 x，则 x 不是素数。我们只需要检查到 sqrt(x)，因为如果 x = a * b，那么必定存在一个 a <= sqrt(x) 和一个 b >= sqrt(x)，因此我们只需要检查较小的因子。

注意：sqrt()方法的计算速度较慢，并且为了防止溢出的问题，建议写成i<=x/i

java"> static boolean get(int x){if(x<2)return false;for(int i=2;i<=x/i;i++){if(x%i==0)return false;}return true;}

二、埃氏筛法

埃氏筛法：

假设所有数都为素数，从 2 开始。
对于每个素数 i，将其所有的倍数标记为合数（即不是素数）。
继续处理下一个未标记的数作为素数，直到遍历到 x。
最终，未被标记的数即为素数。

数据量大于10e7可能会超时

java">    static void get(int x){for(int i=2;i<=x;i++){if(!flag[i]){pri[cnt++]=i;for(int j=i+i;j<=x;j+=i)flag[j]=true;}}}

三、线性筛法

线性筛法是在埃氏筛法的基础上进行优化。

区别：

埃氏筛法：每次遍历素数时都需要标记所有倍数为合数。

线性筛法：只标记 i 与当前已有的素数相乘的倍数（不再处理重复倍数）。这样可以避免多次重复标记，提高效率。

筛法过程：

遍历每个数 i，如果 i 是素数（即 flag[i] == false），则将其加入素数列表。
对于每个素数 p，从 i * p 开始标记合数，直到 x。
注意标记时，若 i 已经被 p（一个较小的素数）整除，则不再继续与更大的素数进行标记，避免重复。

java">import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;public class Main {static int N=1000010;static List<Integer> list=new ArrayList<>();static boolean flag[]=new boolean[N];public static void main(String[] args) throws IOException {Read sc=new Read();int n=sc.nextInt();get(n);System.out.println(list.size());}static void get(int n){for(int i=2;i<=n;i++){if(!flag[i])list.add(i);for(int j=0;list.get(j)<=n/i;j++){flag[list.get(j)*i]=true;if(i%list.get(j)==0)break;}}}
}class Read{StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() throws IOException {st.nextToken();return (int)st.nval;}
}