Java Program za provjeru prostih brojeva s primjerom

Što je prosti broj?

Prost broj je prirodni broj veći od 1 koji je djeljiv samo s 1 ili samim sobom. Na primjer, 11 je djeljiv samo s 1 ili samim sobom. Ostali prosti brojevi su 2, 3, 5, 7, 11, 13, 17, a niz se nastavlja beskonačno.

Broj veći od 1 koji nije prost naziva se složeni broj jer se može sastaviti od manjih faktora. Vrijednost 9 je složena jer se dijeli s 3, a 15 je složena jer se dijeli s 3 i 5.

Bilješka: 0 i 1 nisu prosti brojevi. 2 je jedini paran prosti broj, a negativne vrijednosti se nikada ne smatraju prostim brojevima.

Kako provjeriti je li broj prost u Java

Strategija provjere je jednostavan test djeljivosti. Uzmite kandidatsku vrijednost, podijelite je redom sa svakim manjim cijelim brojem i provjerite ostatak koji vraća operator modula. Ostatak nula dokazuje da djelitelj postoji, što odmah diskvalificira broj.

Programska logika:

• Moramo podijeliti ulazni broj, recimo 17, s vrijednostima od 2 do 17 i provjeriti ostatak. Ako je ostatak 0, broj nije prost.
• Nijedan broj nije djeljiv s više od polovine samog sebe. Dakle, trebamo petlja kroz samo numberToCheck/2Ako je ulaz 17, polovica je 8.5 i petlja će iterirati kroz vrijednosti od 2 do 8.
• Ako je brojZaProvjeru potpuno djeljiv s drugim brojem, zastavica jePrim se postavlja na false i izašlo se iz petlje.

Dva Java Značajke nose cijeli algoritam. Operator modula % vraća ostatak cjelobrojnog dijeljenja, a break Naredba zaustavlja petlju čim je odgovor poznat, tako da se ne izvršavaju nepotrebne iteracije.

Java Program za provjeru je li broj prost ili ne

Program u nastavku dodjeljuje vrijednost 17 varijabli numberToCheck i ispisuje svaki korak dijeljenja, tako da možete pratiti zaključivanje redak po redak. Kod se može uređivati, stoga promijenite vrijednost i ponovno ga pokrenite sa složenim brojem kao što je 21 kako biste vidjeli suprotan ishod.

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

Očekivani rezultat:

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

Petlja se zaustavlja na 8 jer 17 podijeljeno s 2 daje 8 u cjelobrojnoj aritmetici. Budući da nijedan ostatak nikada nije bio nula, zastavica isPrime zadržava svoju početnu vrijednost true, a konačni uvjet ispisuje pozitivnu presudu.

Optimizirana provjera prostih brojeva metodom kvadratnog korijena

Dijeljenje do polovice broja je ispravno, ali rasipno. Ako broj n ima djelitelj veći od svog kvadratnog korijena, odgovarajući sudjelitelj mora biti manji od kvadratnog korijena, tako da bi već bio otkriven. Provjera do √n stoga daje isti odgovor s puno manje iteracija.

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

Izlaz:

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

Stanje i * i <= n izbjegava poziv funkcije Math.sqrt s pomičnim zarezom, a korak 2 preskače svaki parni djelitelj. Za vrijednost kao što je 1,000,003 osnovna petlja izvodi otprilike 500,000 iteracija, dok ova verzija izvodi manje od 500.

Provjera prostog broja koji je unio korisnik

Tvrdo kodirani unos je prikladan za demonstracije, no stvarne vježbe obično zahtijevaju unos s tipkovnice. Klasa Scanner čita cijeli broj iz konzole i prosljeđuje ga istoj metodi 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();
    }
}

Uzorak:

Enter a number: 29
29 is a Prime number

Uobičajene pogreške pri pisanju programa za proste brojeve

Većina netočnih slanja ne uspijeva na graničnim vrijednostima, a ne u glavnoj petlji. Donji popis pokriva pogreške koje se najčešće pojavljuju u početničkom kodu.

1. Pokretanje petlje od 1: Svaki cijeli broj se dijeli s 1, pa se zastavica odmah postavlja na false i program izvještava da nijedan broj nije prost.
2. Tretiranje 1 kao prostog broja: Vrijednost 1 ima samo jednog djelitelja, stoga ne zadovoljava definiciju dva djelitelja i mora vratiti false.
3. Izostavljanjem naredbe break: Program i dalje vraća točan odgovor, ali nastavlja s iteracijama nakon što je presuda poznata, što gubi vrijeme na velike ulazne podatke.
4. Korištenje i <= n kao granica: Broj se uvijek dijeli sa samim sobom, pa se petlja mora zaustaviti prije nego što se dođe do n.
5. Usporedba s = umjesto ==: Jedan znak jednakosti dodjeljuje vrijednost umjesto da je provjerava, što stvara grešku prilikom kompajliranja u if uvjetu.

Usporedba metoda provjere primarnih vrijednosti

Odaberite metodu koja odgovara veličini ulaza i treba li testirati jednu vrijednost ili cijeli raspon.

Kada se mora klasificirati cijeli raspon, a ne samo jedna vrijednost, sito je daleko učinkovitije. Naš prateći program za pronalaženje Glavni Numbers od 1 da 100 pokazuje taj obrazac. Za povezane vježbe vođene petljama, pregledajte Fibonaccijev niz u Java je Java palindromski program, A Bubble Algoritam sortiranja u JavaPočetnici kojima je potrebno osvježenje znanja o deklariranju zastavice i brojača trebali bi pročitati o Java varijable u glavnom Java udžbenik.

Pitanja i odgovori