Java Програма за проверка на просто число с пример

Какво е просто число?

Простото число е естествено число, по-голямо от 1, което се дели само на 1 или на себе си. Например, 11 се дели само на 1 или на себе си. Други прости числа са 2, 3, 5, 7, 11, 13, 17 и поредицата продължава безкрайно.

Число, по-голямо от 1, което не е просто, се нарича съставно число, защото може да бъде съставено от по-малки делители. Числото 9 е съставно, защото се дели без остатък на 3, а числото 15 е съставно, защото се дели без остатък на 3 и 5.

Забележка: 0 и 1 не са прости числа. 2 е единственото четно просто число и отрицателните стойности никога не се считат за прости.

Как да проверим дали едно число е просто в Java

Стратегията за проверка е директен тест за делимост. Вземете кандидат-стойността, разделете я на всяко по-малко цяло число поред и проверете остатъка, върнат от оператора на модула. Остатък от нула доказва съществуването на делител, което веднага дисквалифицира числото.

Програмна логика:

• Трябва да разделим входно число, например 17, от стойности от 2 до 17 и да проверим остатъка. Ако остатъкът е 0, числото не е просто.
• Никое число не се дели на повече от половината от себе си. Така че имаме нужда контур чрез просто numberToCheck/2Ако входът е 17, половината е 8.5 и цикълът ще итерира през стойностите от 2 до 8.
• Ако numberToCheck е напълно делимо на друго число, флагът isPrime се задава на false и цикълът е излязъл.

две Java характеристиките носят целия алгоритъм. Операторът на модул % връща остатъка от целочислено деление и break Операторът спира цикъла веднага щом отговорът е известен, така че не се изпълняват ненужни итерации.

Java Програма за проверка дали дадено число е просто или не

Програмата по-долу присвоява стойността 17 на променливата numberToCheck и отпечатва всяка стъпка на деление, така че можете да следвате разсъжденията ред по ред. Кодът е редактируем, така че променете стойността и го изпълнете отново със съставно число, като например 21, за да видите обратния резултат.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Очакван резултат:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

Цикълът спира на 8, защото 17 делено на 2 е равно на 8 в целочислена аритметика. Тъй като никой остатък никога не е бил нула, флагът isPrime запазва началната си стойност true и крайното условие отпечатва положителната присъда.

Оптимизирана проверка на прости числа с помощта на метода на квадратен корен

Деленето до половината от числото е правилно, но е разточително. Ако числото n има делител, по-голям от корен квадратен, съответстващият коделител трябва да е по-малък от корен квадратен, така че той вече би бил открит. Следователно проверката до √n дава същия отговор с много по-малко итерации.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Изход:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

Състоянието i * i <= n избягва извикване на Math.sqrt с плаваща запетая, а стъпката 2 пропуска всеки четен делител. За стойност като 1 000 003 основният цикъл изпълнява приблизително 500 000 итерации, докато тази версия изпълнява по-малко от 500.

Проверка на просто число, въведено от потребителя

Твърдо кодираният вход е удобен за демонстрации, но реалните упражнения обикновено изискват въвеждане от клавиатурата. Класът Scanner чете цяло число от конзолата и го предава на същия метод isPrime.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Примерно изпълнение:

Enter a number: 29
29 is a Prime number

Често срещани грешки при писане на програма за прости числа

Повечето неправилни изпълнения се провалят при гранични стойности, а не в главния цикъл. Списъкът по-долу обхваща грешките, които се появяват най-често в код за начинаещи.

1. Започване на цикъла от 1: Всяко цяло число се дели на 1, така че флагът веднага се задава на „false“ и програмата съобщава, че никое число не е просто.
2. Третиране на 1 като просто число: Стойността 1 има само един делител, така че не отговаря на дефиницията за два делителя и трябва да върне false.
3. Пропускане на оператора break: Програмата все още връща правилния отговор, но продължава да итерира, след като присъдата е известна, което губи време с големи входни данни.
4. Използването на i <= n като границата: Числото винаги се дели на себе си, така че цикълът трябва да спре преди да достигне n.
5. Сравняване с = вместо ==: Единичен знак за равенство присвоява стойност, вместо да я проверява, което води до грешка по време на компилация в условието if.

Сравнение на методите за проверка на първични данни

Изберете метода, който съответства на размера на входните данни и дали трябва да се тества една стойност или цял диапазон.

Когато трябва да се класифицира цял диапазон, а не само една стойност, ситото е много по-ефективно. Нашата съпътстваща програма за намиране Основен Numbers от 1 да 100 демонстрира този модел. За свързани упражнения, задвижвани от цикли, прегледайте Серия на Фибоначи в Java- Java палиндромна програмаи Bubble Алгоритъм за сортиране в JavaНачинаещите, които се нуждаят от опресняване на знанията за декларирането на флага и брояча, трябва да прочетат за Java променливи в главното Java настойнически.

Въпроси и Отговори