001    package de.hska.java.aufgaben.rekursion;
002    
003    /**
004     * Rekursive Implementierung eines Brute-Force-Primzahltests.
005     * <p>
006     *   <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/rekursion.html#primzahl">Zurück zum Aufgabentext</a>
007     * </p>
008     * @author Christian Pape
009     *
010     */
011    public class Primzahl {
012    
013            /**
014             * Gibt genau dann true zurück, wenn n
015             * eine Primzahl ist.
016             * Die Methode hat im schlimmsten Fall
017             * einen Zeitaufwand von O(n).
018             * Aufgrund der linearen Rekursion, kann 
019             * es schon bei ab  n > 10 000 ein
020             * StackOverflowError geworfen werden.
021             * 
022             * @param n eine natürliche Zahl grösser 1
023             */
024            public boolean istPrimzahl(long n) {
025                    return istPrimzahl(n, n - 1);
026            }
027    
028            private boolean istPrimzahl(long n, long m) {
029                    if (m == 1) {
030                            return true;
031                    } else if (n % m == 0) {
032                            return false;
033                    } else {
034                            return istPrimzahl(n, m - 1);
035                    }
036            }
037    
038    }