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 χαρακτηριστικά φέρουν ολόκληρο τον αλγόριθμο. Ο τελεστής modulus % επιστρέφει το υπόλοιπο μιας ακέραιης διαίρεσης, και το 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 φροντιστήριο.

Συχνές Ερωτήσεις