基础数学知识

1.判断一个数是不是质数（素数）

public static boolean isPrime(int num) {
	  if(num < 2) {
		  return false;
	  }
	  
	  for(int i = 2; i <= num/i; i++) {
		    if(num % i == 0) {
		    	return false;
		    }
	  }
	  return true;
}

2.筛质数

import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] ans = new int[n];
        int[] nums = new int[n];
        for(int i =0 ;i < n;i++) {
        	nums[i] = sc.nextInt();
        } 
        int k = 0;
        for(int i = 0;i < n;i++) {
        	 if(isvalid(nums[i])) {
        		  ans[k++] = nums[i];
        	 }
        } 
        
        for(int i = 0;i < k;i++) {
        	System.out.print(ans[i]+" ");
        }
    }

3.分解质因数

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			int temp = sc.nextInt();
			isPrime(temp);
		}
	}
	
	public static void isPrime(int n) {
		for(int i=2;i<=Math.sqrt(n);i++) {
			int count=0;
			while(n%i==0) {
				n/=i;
				count++;
			}
			if(count!=0) 
               System.out.println(i+" "+count);
	   }
	//最后如果n还是>1，说明这就是大于sqrt(n)的唯一质因子，输出即可。
		if(n>1) {
			System.out.println(n+" "+1);
		}
		System.out.println();

}
}

 3.求约数（因数）

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while(n--!=0) {
			int a=sc.nextInt();
			isyueshu(a);
		}
	}
	
	public static void isyueshu(int n) {
		 List list=new ArrayList<>();
		
		for(int i=1;i<=Math.sqrt(n);i++) {
			if(n%i==0) {
				//将i添加进去
				list.add(i);
				//约数都是成对的,所以n/i也是它的约数
				if(n/i!=i) list.add(n/i);
			}
		}
		Collections.sort(list);
		for (Integer integer : list) {
			System.out.print(integer+" ");
		}
		System.out.println();
	}

}

4.求最大公约数（欧几里得算法）

 public static int getGCD(int num1, int num2) {
        // 先获得绝对值，保证负数也可以求
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        // 先求余数，假定第一个数较大；如果第二个较大，在第二轮调用时会颠倒过来
        int remainder = num1 % num2;
        // 如果为 0，则直接得出
        if (remainder == 0) {
            return num2;
        }
        // 递归调用
        return getGCD2(num2, remainder);
    }