How to find Java prime numbers

What is a prime number?

When I try to tackle the problems of competitive professionals, I can't remember what I learned when I was a student.

Prime numbers, according to Wikipedia

A prime number is a natural number that is greater than 1 and has only 1 positive divisor and itself. It can also be rephrased as a natural number whose number of positive divisors is 2.

That's right. In other words, it's an integer greater than ** 1, a number that can only be divided by 1 and yourself **.

Primality test program

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "Is not a prime number.");
      return;
    }

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "Is not a prime number.");
        return;
      }
    }
    
    System.out.println(target + "Is a prime number.");
  }
}

Commentary

Integer greater than 1

    if (target < 2) {
      System.out.println(target + "Is not a prime number.");
      return;
    }

Here, we are checking whether it is an integer ** that is greater than ** 1, which is meaningful because it is a prime number. If it is less than 2, you know that it is not a prime number, so output it and finish the process immediately.

A number that can only be divided by 1 and yourself

After all it is this part that becomes the liver.

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "Is not a prime number.");
        return;
      }
    }
    
    System.out.println(target + "Is a prime number.");

In the for statement, divide by the number from 2 to target-1 one by one and check if it is divisible. If there is even one divisible number, that number is not a prime number, so output it and end the process with return.

If no number is divisible, then target is a prime number. : clap:

Speeding up

As a simple way to find out if it is a prime number, I used the above method of dividing by 1 and all numbers except the target number. However, with this method, the larger the number of objects to be examined, the longer the calculation will take.

So, as you said in the comment, it seems that you can judge whether it is a prime number or not by checking only the value below the square root.

Why square root is all right

A prime number is a number that can only be divided by 1 and itself, but other numbers are called composite numbers. In other words, a composite number is a number that is neither 1 nor a prime number. In other words, the composite number is ** 1 and has at least one divisor other than itself **.

In addition, the composite number has the property of ** having a divisor of ** √n or less.

Composite number has divisors less than or equal to √n

Why can we say that composite numbers have divisors less than or equal to √n?

First, the composite number n can be expressed as n = ab because there are natural numbers a and b that are not 1. If n does not have a divisor less than or equal to √n, then √n <a, √n <b. Since √n is greater than 0, if √n <a, √n <b (when n does not have a divisor less than or equal to √n),√n√n (= n)is ʻab. It will be smaller, which is contrary to n = ab`. Therefore, it can be said that n has a divisor of √n or less.

In other words, if n is a composite number, it has a divisor of √x or less, so if you check if there is a divisor of √x or less, You can determine if the number is a prime number!

Primality test program

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "Is not a prime number.");
      return;
    }
    if (target % 2 == 0) { //Even numbers return first
      System.out.println(target + "Is not a prime number.");
      return;
    }

    for (int i = 3; i <= Math.sqrt(target); i+=2) {
      if (target % i == 0) {
        System.out.println(target + "Is not a prime number.");
        return;
      }
    }

    System.out.println(target + "Is a prime number.");
  }
}