Проверка простых чисел на Java

Question

Я новичок в программировании и в настоящее время изучаю Java. Кто-нибудь может мне помочь, как проверить, является ли число простым с помощью цикла for? Спасибо заранее!

Answer 1

Я предлагаю вам прочитать ответ @Neng Liu снизу вверх и попытаться понять все алгоритмы. Однако вы можете проверить этот код для второго алгоритма из ответа @Neng Liu.

import java.util.Scanner;


public class PrimeNumber{
    public static void main(String [] args){
       int number,i,rem;
       boolean flag = true;
       Scanner input = new Scanner(System.in);
       System.out.print("Enter an integer to check if its PRIME number : ");
       number = input.nextInt();
       if(number >= 2){
           for(i = 2; 2 * i < number; i++){
               rem = number % i;
               if(rem == 0){
                   flag = false;
                   break;
               }
           }
           if(flag){
               System.out.println(number+" is a Prime number");
           }else{
               System.out.println(number+" is not Prime number");
           }
       }else{
           System.out.println("1 & Negative numbers can't be prime ! ");
       }

    }
}

Answer 2

Вот простая программа для проверки, является ли число простым или нет;

import java.util.*;
class Example{
public static void main(String args[]){
    Scanner input=new Scanner(System.in);
    int count=0;
    System.out.print("Input a Number : ");
    int num=input.nextInt();
    for(int i=2;i<num;i++){
        if(num%i==0){count++;}
    }
    if(num>1&count==0){
        System.out.print("\nIt Is a Prime Number.");
    }
    else{
        System.out.print("\nIt Is a Not Prime Number.");
    }
}

}

Answer 3

С этого сайта.

Мы узнали, что числа простые, если у них есть только делители 1 и сам. Тривиально, мы можем проверить каждое целое число от 1 до самого себя (исключительное) и проверить, делится ли оно равномерно.

Например, может возникнуть искушение запустить этот алгоритм:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

---

Поначалу это не кажется плохим, но мы можем сделать это быстрее - намного быстрее. Предположим, что если 2 делит некоторое целое число n, то (n / 2) также делит n. Это говорит нам о том, что нам не нужно пробовать все целые числа от 2 до n. Теперь мы можем изменить наш алгоритм:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for (int i = 2; 2 * i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

---

При более эффективном кодировании мы замечаем, что вам действительно нужно перейти только к квадратному корню из n, потому что если вы перечислите все факторы числа, квадратный корень всегда будет посередине (если это не целое число, мы по-прежнему в порядке, мы могли бы быть слишком приблизительными, но наш код все еще будет работать).

Наконец, мы знаем, что 2 - это «самое странное» простое число - оно оказывается единственным четным простым числом. Из-за этого нам нужно только проверить 2 отдельно, затем пройти нечетные числа до квадратного корня из n. В итоге наш код будет выглядеть примерно так:

//checks whether an int is prime or not.
boolean isPrime(int n) {
    //check if n is a multiple of 2
    if (n % 2 == 0) return false;
    //if not, then just check the odds
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Как видите, мы прошли путь от проверки каждого целого числа (до n, чтобы узнать, что число простое) до простой проверки половины целых чисел вплоть до квадратного корня (на самом деле, нечетных). Это огромное улучшение, особенно с учетом больших чисел.