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<Integer> 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);
}