【蓝桥杯-筑基篇】基础数学思维与技巧(2)

痛定思痛。 2024-04-20 07:48 80阅读 0赞

> ?系列专栏:[蓝桥杯][Link 1]
> 
> ?个人主页:[个人主页][Link 2]

**目录**

?1.判断素数?

?2.大整数?

?3.求n的约数个数?

?4.数学归纳法?

?5.阶乘之和?

--------------------

#### ?1.判断素数? ####

**素数的定义**

素数又称[质数][Link 3]，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数，否则称为合数（规定1既不是素数也不是合数）

**?方法1：**

遍历从2到n-1的所有数字，判断是否有可以被n整除的数，如果没有，则为素数。

import java.util.Scanner;
    public class A {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入要判断的数字：");
            int n = sc.nextInt();
            int i = 0;
     
            for ( i = 2; i <= n-1 ; i++) {
                if(n % i == 0){
                    System.out.println(n+"不是素数");
                    break;
                }
            }
            if(i == n){
                System.out.println(n+"是素数");
            }
        }
    }

**?方法2：**

判定的范围改为\[2 -,n/2\]。当 i>n/2 时，则判定为素数。

import java.util.Scanner;
    public class A {
     
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入要判断的数字：");
            int n = sc.nextInt();
            int i = 0;
     
            for ( i = 2; i <= n/2 ; i++) {
                if(n % i == 0){
                    System.out.println(n+"不是素数");
                    break;
                }
            }
            if(i > n/2){
                System.out.println(n+"是素数");
            }
        }
    }

**?方法3：**

在Java中判定素数的范围也可以到sqrt(n),(对n开平方)。对应的函数为：Math.sqrt(n)

public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                System.out.println("请输入要判断的数字：");
            while(sc.hasNext()) {
                int n = sc.nextInt();
                int i = 2;
                for(;i <= Math.sqrt(n);i++){
                    if(n % i == 0){
                        System.out.println(n+"不是素数");
                        break;
                    }
                }
                if(i >Math.sqrt(n)){
                    System.out.println(n+"是素数");
                }
    
            }
    		
    	}

**?方法4：**埃氏筛法

[感兴趣的小伙伴看这篇文章][Link 4]

**?方法5：**欧拉筛法

[感兴趣的小伙伴看这篇文章][Link 5]

#### ?2.大整数? ####

在java中范围最大的基本数据类型是long，它可表示的范围是-2的63次方 到 2的63次方-1。当我们遇到要表示的数超过了该范围时就必须使用[BigInteger][]类。

比如我们要[计算n的阶乘][n]。

**BigInteger类的创建：**

BigInteger bigInteger = new BigInteger("1");

**自定义进制：**

BigInteger bigInteger = new BigInteger("1001",2);//2为二进制
    	    	System.out.println(bigInteger);//输出9

**BigInteger类的运算：**

**加法：**

BigInteger a = new BigInteger("10");
    BigInteger b = new BigInteger("2");
    BigInteger add = a.add(b);// 加法
    System.out.println(add);//12

**减法：**

BigInteger subtract = a.subtract(b); // 减法
    System.out.println(subtract);//98

**乘法：**

BigInteger multiply = a.multiply(b); // 乘法
    System.out.println(multiply);//200

**除法：**

BigInteger divide = a.divide(b); // 除法
    System.out.println(divide);//50

**取余：**

BigInteger mod = a.mod(b); // 取余（只返回正数）
    System.out.println(mod);//0

#### ?3.求n的约数个数? ####

例如：求36 的约数

因为：1\*36=36，2\*18=36，3\*12=36，4\*9=36，6\*6=36

故36的约数为：1，36，2，18，3，12，4，9，6

总共：9个

**?方法1：暴力枚举**

public static void main(String[] args) {
    	    	Scanner scanner=new Scanner(System.in);
    	    	while(scanner.hasNext()) {
    	    		int n=scanner.nextInt();
    	    		int count=0;
    	    		for (int i = 1; i <= n; i++) {
    					if(n%i==0) {
    						count++;
    					}
    				}
    	    		System.out.println(count);	
    	    	}
    
    
    	}

**?方法2：**

**由原来i=1 到 i=n 列举 ，变为 i=1 到 i=n/2。**

以36举例，36/2=18 18之后的 19 20 21 22 一直到35 都不是36的约数，只有36是。

故此 只需要求出 n/2之前的 约数数量 然后加1 即可。

图示：

![aeb6238ec64a451792888f66c3e4f3e8.png][]

public static void main(String[] args) {
    	    	Scanner scanner=new Scanner(System.in);
    	    	while(scanner.hasNext()) {
    	    		int n=scanner.nextInt();
    	    		int count=0;
    	    		for (int i = 1; i <= n/2; i++) {
    					if(n%i==0) {
    						count++;
    					}
    				}
    	    		System.out.println(count+1);	
    	    	}
    
    
    	}

#### ?4.数学归纳法? ####

![1a68710bf0a244eb9f6119d06a55d5d6.png][]

嘿嘿嘿，和高中数学很像。

**其核心思想：一个个列举，找出规律，然后用代码实现。**

#### ?5.阶乘之和? ####

输入一个数，判断这个数能不能用互不相等的非负整数的阶乘的和来表示，例如9=1!+2!+3!.

**思路：**

把0到10的阶乘都算出来 然后用数组存取，从10的阶乘开始，一直的比较然后不断的相减，看最后number 是否等于0，为0则是可以的，否则就不行。

public static void main(String[] args) {
    
    	    	int arr[]= new int[10];//arr数组用于存阶乘
    	    	int fac=1;
    	    	for (int i = 1; i <=10; i++) {
    				fac=fac*i;
    				arr[i-1]=fac;
    			}
    //	    	System.out.println(Arrays.toString(arr));
    	    	Scanner scanner=new Scanner(System.in);
    	    	while(scanner.hasNext()) {
    	    		int number=scanner.nextInt();
    	    		
    	    		if(number<0) {
    					System.out.print("no");
    				     break;
    				}
    	    		
    	    		for (int i =arr.length-1 ; i >=0 ; i--) {
    					
    					if(number>=arr[i]) {
    						number=number-arr[i];
    					}
    				
    				}
    	
    				if(number==0) {
    					System.out.println("yes");
    				
    				}
    				else System.out.println("无解");
    	    
    	    	}
    	    	
    
    
    	}

[Link 1]: https://blog.csdn.net/javascript_tsj/category_12167433.html
[Link 2]: https://blog.csdn.net/Javascript_tsj?type=blog
[Link 3]: https://so.csdn.net/so/search?q=%E8%B4%A8%E6%95%B0&spm=1001.2101.3001.7020
[Link 4]: https://blog.csdn.net/GoodburghCottage/article/details/125912135?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%9F%83%E6%B0%8F%E7%AD%9B%E6%B3%95&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-125912135.142%5Ev73%5Einsert_down4,201%5Ev4%5Eadd_ask,239%5Ev2%5Einsert_chatgpt&spm=1018.2226.3001.4449
[Link 5]: https://blog.csdn.net/m0_57071296/article/details/119873446?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167842889016800186532490%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167842889016800186532490&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119873446-null-null.142%5Ev73%5Einsert_down4,201%5Ev4%5Eadd_ask,239%5Ev2%5Einsert_chatgpt&utm_term=%E6%AC%A7%E6%8B%89%E7%AD%9B%E6%B3%95&spm=1018.2226.3001.4187
[BigInteger]: https://so.csdn.net/so/search?q=BigInteger&spm=1001.2101.3001.7020
[n]: https://so.csdn.net/so/search?q=%E8%AE%A1%E7%AE%97n%E7%9A%84%E9%98%B6%E4%B9%98&spm=1001.2101.3001.7020
[aeb6238ec64a451792888f66c3e4f3e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/81e122b641204c1291c27a0519d872e8.png
[1a68710bf0a244eb9f6119d06a55d5d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/38344778789d455db636b6e541744c4a.png