Java Ohjelma alkuluvun tarkistamiseen esimerkin avulla

Mikä on alkuluku?

Alkuluku on luonnollinen luku, joka on suurempi kuin 1 ja joka on jaollinen vain luvulla 1 tai itsellään. Esimerkiksi luku 11 on jaollinen vain luvulla 1 tai itsellään. Muita alkulukuja ovat 2, 3, 5, 7, 11, 13, 17, ja lukujono jatkuu loputtomasti.

Lukua, joka on suurempi kuin 1 ja joka ei ole alkuluku, kutsutaan yhdistetyksi luvuksi, koska se voidaan muodostaa pienemmistä tekijöistä. Luku 9 on yhdistetty luku, koska se on tasan jaettu 3:lla, ja luku 15 on yhdistetty luku, koska se on tasan jaettu 3:lla ja 5:llä.

Huomautus: 0 ja 1 eivät ole alkulukuja. 2 on ainoa parillinen alkuluku, ja negatiivisia arvoja ei koskaan pidetä alkulukuina.

Kuinka tarkistaa, onko luku alkuluku Java

Todennusstrategia on suoraviivainen jaollisuustesti. Ota ehdokasarvo, jaa se vuorollaan jokaisella pienemmällä kokonaisluvulla ja tutki modulusoperaattorin palauttamaa jakojäännöstä. Nollan jakojäännös todistaa, että jakaja on olemassa, mikä välittömästi hylkää luvun.

Ohjelman logiikka:

• Meidän täytyy jakaa syöttöluku, esimerkiksi 17, lukujen 2 ja 17 välillä ja tarkistaa jakojäännös. Jos jakojäännös on 0, luku ei ole alkuluku.
• Mikään luku ei ole jaollinen enemmän kuin puolella itsestään. Joten meidän täytyy silmukka kautta vain numberToCheck/2Jos syöte on 17, puolikas on 8.5 ja silmukka iteroituu arvojen 2–8 läpi.
• Jos numberToCheck on täysin jaollinen toisella luvulla, lippu isPrime asetetaan arvoon false ja silmukka poistuu.

Kaksi Java ominaisuudet kantavat koko algoritmin. Modulusoperaattori % palauttaa kokonaislukujakamisen jakojäännösosan ja break lauseke pysäyttää silmukan heti, kun vastaus on tiedossa, joten turhia iteraatioita ei suoriteta.

Java Ohjelma, joka tarkistaa, onko luku alkuluku vai ei

Alla oleva ohjelma antaa muuttujalle numberToCheck arvon 17 ja tulostaa jokaisen jakolaskuaskeleen, jotta voit seurata päättelyä rivi riviltä. Koodia voi muokata, joten muuta arvoa ja suorita se uudelleen yhdistetyllä luvulla, kuten 21, nähdäksesi päinvastaisen tuloksen.

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");
    }
  }

Odotettu tuotos:

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

Silmukka pysähtyy lukuun 8, koska kokonaislukuaritmetiikassa 17 jaettuna 2:lla on yhtä kuin 8. Koska mikään jakojäännös ei ole koskaan ollut nolla, isPrime-lippu pitää alkuarvonsa true ja loppuehto tulostaa positiivisen tuloksen.

Optimoitu alkulukutarkistus neliöjuurimenetelmällä

Luvun jakaminen puolella on oikein, mutta tuhlausta. Jos luvun n jakaja on suurempi kuin sen neliöjuuri, vastaavan yhteisjakajan on oltava pienempi kuin neliöjuuri, joten se olisi jo löydetty. Tarkistaminen √n:ään asti tuottaa siis saman vastauksen paljon vähemmillä iteraatioilla.

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));
        }
    }
}

lähtö:

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

Kunto i * i <= n välttää liukulukukutsun funktiolle Math.sqrt, ja kahden askel ohittaa jokaisen parillisen jakajan. Arvolla, kuten 1 000 003, perussilmukka suorittaa noin 500 000 iteraatiota, kun taas tämä versio suorittaa alle 500.

Tarkista käyttäjän syöttämä alkuluku

Kovakoodattu syöttö on kätevää demonstraatioissa, mutta oikeissa harjoituksissa yleensä vaaditaan näppäimistösyöttöä. Scanner-luokka lukee kokonaisluvun konsolista ja välittää sen samalle isPrime-metodille.

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();
    }
}

Näyteajo:

Enter a number: 29
29 is a Prime number

Yleisiä virheitä alkulukuohjelman kirjoittamisessa

Useimmat virheelliset lähetykset epäonnistuvat raja-arvojen perusteella pääasiallisen silmukan sijaan. Alla oleva luettelo kattaa virheet, joita esiintyy useimmin aloittelijan koodissa.

1. Silmukan aloittaminen kohdasta 1: Jokainen kokonaisluku on jaollinen ykkösellä, joten lippu asetetaan välittömästi arvoon epätosi ja ohjelma raportoi, ettei mikään luku ole alkuluku.
2. Käsittelemällä 1 alkulukuna: Arvolla 1 on vain yksi jakaja, joten se ei läpäise kahden jakajan määritelmää ja sen on palautettava arvon false.
3. Katkaisulausekkeen poisjättäminen: Ohjelma palauttaa edelleen oikean vastauksen, mutta iterointi jatkuu vielä tuomion tiedostamisen jälkeen, mikä tuhlaa aikaa suuriin syötteisiin.
4. Käyttäminen i <= n rajana: Luku jakaa aina itsensä, joten silmukan on loputtava ennen kuin se saavuttaa luvun n.
5. Vertailuun = sijasta ==: Yksi yhtäsuuruusmerkki määrittää arvon testaamisen sijaan, mikä tuottaa käännösaikaisen virheen if-ehdossa.

Prime Checking -menetelmien vertailu

Valitse menetelmä, joka vastaa syötteen kokoa ja sitä, testataanko yhtä arvoa vai koko aluetta.

Kun kokonainen alue on luokiteltava yhden arvon sijaan, seula on paljon tehokkaampi. Seuraohjelmamme löytää tärkein Numbers alkaen 1 ja 100 osoittaa kyseisen kaavan. Katso aiheeseen liittyviä silmukkapohjaisia ​​harjoituksia Fibonaccin sarja Java, The Java palindromiohjelma, ja Bubble Lajittele algoritmi JavaAloittelijoiden, jotka tarvitsevat kertausta lipun ja vastamerkin julistamisesta, kannattaa lukea aiheesta Java muuttujat pääasiassa Java oppitunti.

UKK