Java syntax example analysis

1, n kinds of realms of solving prime numbers

1.1, violent cycle solution

public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j < i;j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数！");
            }
        }
    }
}

1.2, try to divide the first half of the number

public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j < i/2;j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数！");
            }
        }
    }
}

We can find that we can’t solve any number It can be split into the multiplication of two numbers, such as 16: it can be 1 16, 2 * 8, 4 * 4. You can see that the first half of the number is less than half of itself, so we only need to detect this Can the first half of the number be divisible by itself? Because as long as there is one in the first half, there must be a number in the second half that can be multiplied by itself to get itself, so this reduces the workload by half. *

1.3, try to divide the number that is smaller than the root sign of itself

import java.lang.Math;
public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j <= (int)(Math.sqrt(i));j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数！");
            }
        }
    }
}

It is still the same principle as before, but the range is narrowed again, because a number is divided into the product of two numbers In the form of Seeing that it is impossible to have a number that can be multiplied by another number to equal 16, of course 2 * 8, 8 * 2 can only be considered the former one

1.4, look for # in odd numbers ##

import java.lang.Math;
public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 1;i <= 100;i += 2){//从1开始,产生到100的奇数
            int flg = 1;//假设是素数
            if(i == 1){
                System.out.println((i+1) + "是素数！");//2这里需要单拎出来考虑，比较特殊
                continue;
            }
            for(int j = 2;j <= (int)(Math.sqrt(i));j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数！");
            }
        }
    }
}

We know that, except for the special case of 2, all even numbers cannot be prime numbers, because they can at least be divisible by 2. Therefore, when considering within the range, we only need to detect odd numbers. Reduce the number of outer loops.

In fact, there are ways to continue optimizing, so I won’t list them all here. If you are interested, you can check them out. Many bloggers have written very detailed and in-depth articles!

Second, the leap year problem

public class TestDemo220427 {
    public static boolean isleapYear(int year){
        if((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)){
            return true;
        } else{
            return false;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入年份：");
        int year = scan.nextInt();
        boolean ret = isleapYear(year);
        if(ret == true){
            System.out.println(year + "是闰年！");
        }else{
            System.out.println(year + "不是闰年！");
        }
    }
}

Here you only need to know the judgment criteria of leap year to solve the problem well.

Three, find the greatest common divisor and the least common multiple

3.1, find the greatest common divisor

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int m = 0;
        while((m = a%b) != 0){//辗转相除法
            a = b;
            b = m;
        }
        System.out.println(b);
    }
}

3.2, find the least common multiple

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        for(int i = 1;i > 0;i++){
            if((a*i)%b == 0){
                System.out.println("最小公倍数：" + a*i);
                break;
            }
        }
    }
}

In fact, there is another one Formula, assuming that the greatest common divisor is m, then the least common multiple is (a*b)/m.

4. Self-exponentiation problem

import java.lang.Math;
public class TestDemo220427 {
    public static boolean isNarnum(int num,int count){
        int sum = 0;
        int tmp = num;
        while(tmp != 0){
            sum += Math.pow(tmp%10,count);
            tmp /= 10;
        }
        if(sum == num){
            return true;
        }else{
            return false;
        }
    }
    public static void main(String[] args) {
//        判断一个数是不是自幂数
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num = scan.nextInt();
        int count = 0;
        int tmp = num;
        while(tmp != 0){
            count++;
            tmp /= 10;
        }
        boolean ret = isNarnum(num,count);
        if(ret == true){
            System.out.println(num + "是一个" + count +"位自幂数！");
        }else{
            System.out.println(num + "不是自幂数！");
        }
    }
}

5. Count the number of 1’s in binary bits

5.1, circular right shift bitwise AND 1

import java.util.Scanner;
public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        while(num != 0){//右移后不为0就继续统计
            if((num& 1) == 1){
                count++;
            }
            num = num >> 1;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 ：" + ret);
    }
}

Note: There is a bug in this code, because negative numbers cannot be counted. The highest sign bit of the binary system of a negative number is 1. If you shift the sign bit to the right, you will always add 1 to the high bit, and the loop will be endless.

Solution: num = num >> 1 ——> Change to num = num >>> 1, use unsigned right shift, so that the high bits will only be filled with 0. Applies to both positive and negative numbers.

Expansion: Some people may ask, since you can move to the right, why can't you move to the left?

The answer is: It is indeed possible to shift left, but it is not recommended because the efficiency is too low.

public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        for(int i = 0;i < 32;i++){
            if((num & (1 << i)) != 0){
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 ：" + ret);
    }
}

At this time, instead of shifting the number to the left, we shift 1 to the left, and then perform a bitwise AND with the number, because the result can only be 0 or non-0, non-0 It means that the position of 1 in the result of shifting 1 to the left corresponds to the position of this number, so we will count it at this time. Although this method can also solve the problem, you need to shift left 32 times because you have no way of knowing how many 1's there are in front of this number and can only compare all the bits.

5.2, The principle of n & (n-1) eliminating 1

import java.util.Scanner;
public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        while(num != 0){
            num = num&(num-1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 ：" + ret);
    }

This method can be used for both positive and negative numbers, and it is very efficient, bitwise and num-1 once each time , a 1 will be eliminated.

Extension: Use this method to determine whether a certain number is 2 raised to the kth power.

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int num = scan.nextInt();
        if((num & (num-1)) == 0){
            System.out.println("是2的k次方数！");
        }else{
            System.out.println("不是2的k次方数！");
        }
    }
}

The above is the detailed content of Java syntax example analysis. For more information, please follow other related articles on the PHP Chinese website!