一、求某個整數的正約數個數與正約數之和

1.1求某個正整數N的正約數個數?

public class Main {public static void main(String[] args) {System.out.println(count(360));//結果為24}public static long count(long number){long count=1;for(long i=2;i<=Math.sqrt(number);i++){long n=0;while (number%i==0){number=number/i;n++;}if(n>0){count=count*(n+1);}}if(number>1){count=count*2; //處理的是1次冪的情況，因為（1+1）=2；}return count;}
}

?1.2求某個正整數N的正約數之和?

public class Main {public static void main(String[] args) {System.out.println(count(360));}public static long count(long number) {long sum = 1;for (long i = 2; i <= Math.sqrt(number); i++) {long exponent = 0;while (number % i == 0) {number /= i;exponent++;}if (exponent > 0) {// 正確使用等比數列求和公式計算某個質因數對應的約數和long termSum = (long) ((Math.pow(i, exponent + 1) - 1) / (i - 1));// 累乘不同質因數對應的約數和sum *= termSum;}}//處理指數為1的情況，因為number的1次方是number,0次方是1if (number > 1) {sum *= (number + 1);}return sum;}
}

二、求最大公約數

public static long gcd(long a,long b) {while(b!=0) {long temp=b;b=a%b;a=temp;}return a;}

三、分解質因數

 public static void ps(int n) {List<Integer> list=new ArrayList<>();for(int i=2;i<=Math.sqrt(n);i++) {while(n%i==0) {list.add(i);  //找到一個質因數n=n/i;  //更新待分解的數}}if(n>1) {list.add(n); //如果最后余數大于1，則說明它本身也是質數}
}

四、快速冪

import java.util.Scanner;public class a {public static void main(String[] args) {Scanner scan=new Scanner(System.in);long b=scan.nextInt();long p=scan.nextInt();long k=scan.nextInt();System.out.println(quickmi(b,p,k));}public static long quickmi(long b,long p,long k){long res=1;while(p>0){if((p&1)==1){res=res*b%k;}b=b*b%k;p=p>>1;}return res;}}

?五、費馬小定理

乘法逆元的定義

?

import java.util.Scanner;public class a {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();while (n-- > 0) {long b=scan.nextLong();long p=1000000007-2;long k=1000000007;System.out.println(quickmi(b,p,k));}}public static long quickmi(long b,long p,long k){long res=1;while(p>0){if((p&1)==1){res=res*b%k;}b=b*b%k;p=p>>1;}return res;}}

五，求組合數問題(注意看數據范圍，不同范圍不同求法）

?

import java.util.Scanner;public class Main {static long[] arr=new long[16];public static void main(String[] args) {Scanner scan=new Scanner(System.in);int q=scan.nextInt();arr[0]=1;arr[1]=1;for(int i=2;i<16;i++) {arr[i]=i*arr[i-1];}while(q-->0) {int n=scan.nextInt();int m=scan.nextInt();System.out.println(jiec(n,m));}}public static long jiec(int n,int m) {long ans=arr[n]/(arr[m]*arr[n-m]);return ans;}}    

用快速冪加費馬小定理

import java.util.Scanner;public class Main {static long N=1000000007;static long[] arr;public static void main(String[] args) {Scanner scan=new Scanner(System.in);int a=scan.nextInt();int b=scan.nextInt();arr=new long[3001];arr[0]=1;for(int i=1;i<3001;i++){arr[i]=arr[i-1]*i%N;}System.out.println(jisuan(a,b));}//快速冪,a的b次方public static long quickmi(long a,long b){long ans=1;while(b>0){if((b&1)==1){ans=ans*a%N;}a=a*a%N;b=b>>1;}return ans;}//計算組合數public static long jisuan(int a,int b){long fenmu=arr[b]*arr[a-b]%N;//費馬小定理long sum=quickmi(fenmu,N-2);long ans=arr[a]*sum%N;return ans;}
}

六、素數篩

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class a {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();boolean[] prime = new boolean[n + 1]; //標記是否為素數for (int i = 2; i <= n; i++) {prime[i] = true;}List<Integer> list = new ArrayList<>();  //存素數for (int i = 2; i <= n; i++) {if (prime[i]) {list.add(i);}for (int j = 0; j < list.size() && i * list.get(j) <= n; j++) {//i * list.get(j) <= n這個條件是為了防止數組越界prime[i * list.get(j)] = false;if (i % list.get(j) == 0) {break;}}}System.out.println(list.size());}}