【蓝桥杯】素数判断的常见方法

常规方法

在这里插入图片描述

public static boolean isNumber(int n) {boolean flag=true;for(int i=2;i<n;i++) {if(n%i==0) {flag=false;}}return flag;}

	public static boolean isNumber1(int n) {boolean flag=true;for(int i=2;i*i<=n;i++) {if(n%i==0) {flag=false;}}return flag;}

埃氏筛选法

在这里插入图片描述

	public static int  isNumber3(int N) {int n=2;while(n/Math.log(n)<N) {n++;}int arr[]=new int[n];int x=2;while(x<n) {if(arr[x]!=0) {x++;continue;}int k=2;while(x*k<n) {arr[x*k]=-1;k++;}x++;}int result=0;int sum=0;for(int i=2;i<arr.length;i++) {if(arr[i]==0) {sum++;}if(sum==N) {result=i;break;}}return result;}

质因数分解

	public static Map<Integer, Integer> primeFactor(int num){Map<Integer, Integer> map= new HashMap<Integer, Integer>();for(int i=2;i*i<=num;i++) {while(num%i==0) {Integer v=map.get(i);if(v==null) {map.put(i, 1);}else {map.put(i, v+1);}num=num/i;}}return map;}