常见方法有:
试除法:
朴素筛法O(nlogn):
埃氏筛法O(nloglogn):
线性筛法O(n):
Java代码模板(朴素筛时间复杂度O(nlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); }
static int primes(int n) { boolean st[] = new boolean[n+1]; int prime[] = new int[n+1]; int ans =0; for(int i=2;i<=n;++i) { if(!st[i]) prime[ans++] = i; for(int j = i*2;j<=n;j+=i) { st[j] = true; } } return ans; }
}
|
Javad代码模板(埃氏筛法时间复杂度O(nloglogn),几乎与O(n)持平)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); }
static int primes(int n) { boolean st[] = new boolean[n+1]; int prime[] = new int[n+1]; int ans =0; for(int i=2;i<=n;++i) { if(!st[i]) { prime[ans++] = i; for(int j = 2*i;j <=n;j+=i) { st[j] = true; } } } return ans; } }
|
Java代码模板(线性筛法时间复杂度O(n))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); }
static int primes(int n) { boolean st[] = new boolean[n+1]; int prime[] = new int[n+1]; int ans =0; for(int i= 2;i<=n;++i) { if(!st[i]) prime[ans++] = i; for(int j =0;prime[j]<=n/i;++j) { st[prime[j]*i] = true; if(i%prime[j]==0) break; } } return ans; } }
|
注意点:
prime[cnt++]=i;这行代码的意思是:如果发现i是素数,那么就把它放进prime数组里,同时把计数器加一。
prime[j]<=n/i;和之前的用法一样,如果pj乘以i的值大于n也没有意义了。
内层for循环要做两件事情,分为两个条件判断:
1.如果i除以prime[j](简称pj)不等于0,说明pj不是i的最小质因子,并且可以说明pj比i的最小质因子小。这样,pji的最小值因子就一定是pj,我们不管三七二十一,先把pji这个数筛掉。
2.如果i除以pj等于0,说明pj是i的最小质因子,而我们如果继续把j++的话,那么下一个pj就一定不是当前i的最小质因子了,为了避免后面重复计算造成错误,所以这里要break。
综上所述,无论pj能否整除i,pj*i一定是合数,一定要筛掉。