哪里可以免费做网站,公司网站建设办法,权威发布e站,万州网站建设果园路素数筛
素数筛的作用是筛选出[2,N]范围内的所有素数#xff0c;本次主要讲解两种方法#xff0c;分别是埃氏筛和欧拉筛。证明时会提到唯一分解定理#xff0c;如果不知道的小伙伴可以先去学一学#xff0c;那我们开始啦#xff01;
1.埃氏筛
主要思想#xff1a;当找到…素数筛
素数筛的作用是筛选出[2,N]范围内的所有素数本次主要讲解两种方法分别是埃氏筛和欧拉筛。证明时会提到唯一分解定理如果不知道的小伙伴可以先去学一学那我们开始啦
1.埃氏筛
主要思想当找到一个素数时利用该素数把该素数的所有倍数筛掉。
时间复杂度 O ( n l o g ( l o g ( n ) ) ) O(nlog(log(n))) O(nlog(log(n)))
上代码 //每个数的最小质因子//pre[i]表示i的最小质因子book[1] 1;//记录是否为素数1表示不是素数book[0] 1;for(int i 2;ibook.length;i) {if(book[i]0) {// i是素数筛掉素数的倍数 i2 6 222for(int j ii;jbook.lengthj0;ji) {book[j] 1;} }}问题 为什么遍历到i时若i没有被标记为合数也就是没有被i前面的数筛掉则一定是素数 为什么for循环遍历到sqrt(N)就可以了
先自己想一想哦提示是唯一分解定理。
答案
还记得唯一分解定理吗一个正整数可以用若干个质数表示假设当前正整数是n它可以用质数 p 1 , p 2 . . . p k p_1,p_2...p_k p1,p2...pk表示 p 1 , p 2 . . . p k p_1,p_2...p_k p1,p2...pk一定比q小。假设q是合数那么遍历到qq一定会被 p 1 , p 2 . . . p k p_1,p_2...p_k p1,p2...pk筛掉。如果q是质数呢他只能写出1*q的形式它会被自己筛掉。其实也就是证明sqrt(N)后面的合数一定会被小于sqrt(N)的数筛掉。设 N n N \sqrt{N}nN N nN且 a ∗ b n a*bn a∗bn,若ab则 a n N a\sqrt{n}\sqrt{N} an N 若a是素数则n会被a筛掉若a是合数则a可以继续分解为更小的素数而a和n都会被这个更小的素数筛掉所以即便 N n \sqrt{N}n N n但是仅用小于 N \sqrt{N} N 的数就可以把n筛掉所以可以遍历到sqrt(N)。
2.欧拉筛
主要思想埃氏筛的一部分时间耗在了重复的筛某些合数比如18会被2和3筛掉。欧拉筛保证每个合数只被筛一次因此也保证了 O ( n ) O(n) O(n)的时间复杂度。
时间复杂度 O ( n ) O(n) O(n)
上代码 int count 0;for (int i 2; i 20000005; i) {//线性if (!visit[i]) {//如果i是一个质数prime[count] i;//记录当前已经找出来的所有的质数}for (int j 0; j count i * prime[j] 20000005; j) {visit[i * prime[j]] true;//用prime[j]筛掉了i * prime[j]。if (i % prime[j] 0) break;//保证每个合数只被最小的质因子筛掉}}问题
为什么if语句满足后可以提前退出循环两个for循环嵌套如何实现的线性复杂度
先自己想一想哦提示是prime[j]是i的因子你可以把式子写出来看看。
再讲答案之前先来捋一捋欧拉筛的结构因为它不像埃氏筛那么直接。
首先一个for循环接着如果当前的i是素数则用另一个数组prime存一下这个数组只存素数。
再来一个for循环这个for循环就是用来筛合数的遍历之前找到的所有素数然后筛掉 p r i m e [ j ] ∗ i prime[j]*i prime[j]∗i。当满足if语句时这一轮的筛合数可以提前退出了。
答案
若此时if语句条件满足了则prime[j]是i的因子因此有 i k ∗ p r i m e [ j ] ik*prime[j] ik∗prime[j]。如果此时没有退出for循环会有 p r i m e [ j 1 ] ∗ i prime[j1]*i prime[j1]∗i被prime[j1]筛掉。 p r i m e [ j 1 ] ∗ i p r i m e [ j 1 ] ∗ k ∗ p r i m e [ j ] k ‘ ∗ p r i m e [ j ] prime[j1]*iprime[j1]*k*prime[j]k^*prime[j] prime[j1]∗iprime[j1]∗k∗prime[j]k‘∗prime[j]这说明了什么说明被prime[j1]筛掉的 p r i m e [ j 1 ] ∗ i prime[j1]*i prime[j1]∗i也会被prime[j]筛掉这就重复筛了怎么办我们让每个数都被其最小的质因子筛掉那么这里prime[j]就是 p r i m e [ j 1 ] ∗ i prime[j1]*i prime[j1]∗i最小的质因子因此j就不继续增大了直接退出该循环。因为保证了每个数只被筛一次第二个for循环总共被执行n次所有的数被筛完代码也就结束了。
例题
埃氏筛——最小质因子之和
参考代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;public class 最小质因子之和Easy {
public static void main(String[] args) throws IOException{//进行预处理f();//求2-n每个数对应的最小质因子sum();//求前缀和数组StreamTokenizer sc new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); Scanner scanner new Scanner(System.in);sc.nextToken();int t (int)sc.nval;while(t-- 0) {sc.nextToken();int n (int)sc.nval;System.out.println(res[n]);}
}
static int book[] new int[4000000];
static int pre[] new int[4000000];
private static void f() {//埃氏筛模板//每个数的最小质因子//pre[i]表示i的最小质因子book[1] 1;//记录是否为素数1表示不是素数book[0] 1;for(int i 2;ibook.length;i) {if(book[i]0) {// i是素数筛掉素数的倍数 i2 6 222pre[i] i;//求的是质数的最小质因子for(int j ii;jbook.lengthj0;ji) {if(book[j]0) {pre[j] i;}book[j] 1;}}}}
static long res[] new long[4000000];
private static void sum() {//一次求出i 2- n// 2-i的最小质因子之和前缀和数组可以在Onfor(int i2;ires.length;i) {res[i] res[i-1]pre[i];}
}
}欧拉筛——最小质因子之和困难版
参考代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class 最小质因子之和Hard {public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));int[] prime new int[20000005];int[] f new int[20000005];boolean[] visit new boolean[20000005];int count 0;for (int i 2; i 20000005; i) {//线性if (!visit[i]) {//如果i是一个质数prime[count] i;f[i] i;}for (int j 0; j count i * prime[j] 20000005; j) {visit[i * prime[j]] true;f[i * prime[j]] prime[j];if (i % prime[j] 0) break;}}long[] sum new long[20000005];//前缀和数组for (int i 2; i f.length; i) {//System.out.println(f[i]);sum[i] sum[i - 1] f[i];}int t Integer.parseInt(br.readLine());while (t-- 0) {int n Integer.parseInt(br.readLine());System.out.println(sum[n]);}}
}
