Primzahlen

[beginner_01]

Halllo. Ich muss jetzt ein Programm schreiben das alle Primzahlen ausgibt.
Aber ich habe Problem! die ersten N Primzahlen berechnet ebenfalls mit Hilfe des Siebs des Eratosthenes. Die Zahl N wird dem Programm als Kommandozeilenargument übergeben.

Bsp:

%java Prime 6 <- Könnt Ihr mir Tipps geben????
2
3
5
7
11
13

public class Primezahlen {


public static void main(String[] args) {


int N = Integer.parseInt(args [0]);
boolean[] p = new boolean[N];



for (int i = 2; i<N; i++)

p = true;
for(int i=2; i*i < N; i++) {
if (p) {
for (int n = 2; n*i<N; n++)
p[n*i]=false;
}
}
for (int i =2; i<N; i++) {
if(p)
System.out.println(i+ " is prime");

}
}
}

 

[Landei]

Funktioniert doch einwandfrei, nur dass N die obere Grenze angibt, und nicht die Anzahl der Primzahlen.

Um alle Primzahlen auszugeben, kannst du ganz primitiv auf Probedivisionen gehen, oder - etwas schwieriger - eine "just in time" Siebvariante schreiben, bei der erst dann gesiebt wird, wenn die Zahl drankommt.

Für letzteres sind allerdings Listen wesentlich bequemer:

import java.util.ArrayList;
import java.util.List;

public class Primes {

    public static void main(String[] args) {
        List<int[]> sieves = new ArrayList<int[]>();
        for(int i = 2; ;i++) {
            boolean isPrime = true;
            for(int[] sieve : sieves) {
                while (sieve[0] < i) {
                    sieve[0] += sieve[1]; //wir erhöhen den Siebeintrag, bis er mindestens so groß wie i ist
                }
                if (sieve[0] == i) {
                    isPrime = false;
                }
            }
            if (isPrime) {
                System.out.println(i + " is prime");
                sieves.add(new int[]{i*i,  i}); //neuer Siebeintrag für i
            }
        }
    }
}

Übrigens bitte [ java ] Tags verwenden.

 

[pappawinni]

Also das "Hauptproblem" bei der Umsetzung dürfte sein, dass Arrays in Java mit dem Index 0 beginnen und ein array[N] den maximalen Index N-1 hat.
Der Algorithmus wie er z.B. in Wikipedia beschrieben ist verlangt aber ein "Array [2..N] of boolean".
Jetzt musst du dir überlegen, wie du damit umgehst.
Du könntest z.B. ein array[N+1] deklarieren, hättest damit den maximalen Index N und nutzt dann aber die Elemente mit Index 0 und 1 nicht, oder du dimensionierst ein array[N-1] und verschiebst beim Zugriff auf das Array den Index, greifst also statt auf Element auf Element [i-2] zu.

 

[Landei]

@pappawinni: Lies noch einmal genau, der TO will "alle" Primzahlen ausgegeben haben, es gibt also keine festgesetzte Obergrenze N (nun gut, hier eigentlich Integer.MAX_INTEGER, aber mit BigInteger wäre das auch kein Problem)

 

[pappawinni]

Ich bin davon ausgegangen, dass es um die Umsetzung vom Sieb des Eratosthenes gemäß
Sieb des Eratosthenes ? Wikipedia
geht.
Wenn du da was anderes liest, auch gut.

 

[beginner_01]

Hallo,

Ich muss die Anzahl der Primzahlen programmieren. Ich habe die andere Ansatz.
Bestimme A -> Anzahl der Primzahlen

public class PrimeJava {

 
    public static void main(String[] args) {
        
        int A= Integer.parseInt(args [0]); //Anzahl der Primzahlen
        int N = a*15;
        int b=0;
        boolean[] p = new boolean[N];
        
        for (int i = 0; i <N; i++)
      
         
               p[i] = true;
        for(int i=2; i*i < N; i++) {
            if (p[i]) {
                for (int n = 2; n*i<N; n++)
                    p[n*i]=false;
            }
        }
       for (int i=2; i<N; i++) {
            if (p[i]) {
               if (b < a) {
                    System.out.println(i+ " is prime");
                    b++;
               }
            }
       }
    }
}

Ich würde gern wissen, was habt ihr andere Idee??? andere Möglichkeiten??

 

[beginner_01]

Hallo,

Ich muss die Anzahl der Primzahlen programmieren. Ich habe die andere Ansatz.
Bestimme A -> Anzahl der Primzahlen

public class PrimeJava {

 
    public static void main(String[] args) {
        
        int A= Integer.parseInt(args [0]); //Anzahl der Primzahlen
        int N = a*15;
        int b=0;
        boolean[] p = new boolean[N];
        
        for (int i = 0; i <N; i++)
      
         
               p[i] = true;
        for(int i=2; i*i < N; i++) {
            if (p[i]) {
                for (int n = 2; n*i<N; n++)
                    p[n*i]=false;
            }
        }
       for (int i=2; i<N; i++) {
            if (p[i]) {
               if (b < a) {
                    System.out.println(i+ " is prime");
                    b++;
               }
            }
       }
    }
}

Ich würde gern wissen, was habt ihr andere Idee??? andere Möglichkeiten??

Ist meine Programmierung auch o.K???? Danke im Voraus

 

[pappawinni]

Also ich bin mal nahe an dem Algo "Sieb des Eratosthenes" von Wikipedia geblieben.
Eingeflickt hab ich ne Abschätzung des Suchbereichs die man sicher optimieren könnte.
Primzahlsatz ? Wikipedia
Woher N = a*15 kommt, weiss ich nicht.
Dazu gekommen ist da dann auch der Zähler z, um die Suche dann zu beenden,
wenn die gewünschte Zahl an Primzahlen ausgegeben wurde.

public class PrimeJava {
	// Sieb des Eratosthenes 
	 
    public static void main(String[] args) {
        
        int a= Integer.parseInt(args [0]); //Anzahl der Primzahlen
        int n = getPrimeSearchLimit(a);
        int z=0;
        boolean[] gestrichen = new boolean[n-1];
        
        for (int i = 2; i <= n; i++) {
        	gestrichen[i-2] = false;	
        }
        
        for(int i=2; i <= n; i++) {
            if (!gestrichen[i-2]) {
                z++;
                System.out.println(i+ " ist Primzahl "+z);
                if (z==a) break;
            	for (int j = i*i; j <= n; j+=i) gestrichen[j-2]=true;
            }
        }
    }
    private static int getPrimeSearchLimit(int gesuchteAnzahl){
    	// Abschätzung des Suchbereiches für eine bestimmte Anzahl von Primzahlen
    	int n=1;
    	int q=1;
    	do {
    		n *= 2;
        	q=(int) (n/Math.log(n)*1.1);
    	} while (q < gesuchteAnzahl);
    	return n;    			
    }
}

 

[Landei]

Ach so, du willst bloß die Anzahl. Dann nimm dein allererstes Programm, und zähle sie halt, statt sie auszugeben.

 

[pappawinni]

Nee Landei, er will vorgeben, wieviele Primzahlen ausgegeben werden sollen, denk ich und die sollen dann auch ausgegeben werden. So interpretiere ich das Beispiel:

Bsp:

%java Prime 6 <- Könnt Ihr mir Tipps geben????
2
3
5
7
11
13

Lies halt mal richtig :lol:

 

[Landei]

Na das geht doch mit meinem Code auch - man muss halt nur mitzählen und dann aufhören:

import java.util.ArrayList;
import java.util.List;

public class Primes {

    public static void main(String[] args) {
        int count = args.length == 0 ? 10 : Integer.parseInt(args[0]);
        System.out.println("The first " + count + " prime numbers:");

        List<int[]> sieves = new ArrayList<int[]>();
        for(int i = 2; count > 0;i++) {
            boolean isPrime = true;
            for(int[] sieve : sieves) {
                while (sieve[0] < i) {
                    sieve[0] += sieve[1];
                }
                if (sieve[0] == i) {
                    isPrime = false;
                }
            }
            if (isPrime) {
                System.out.println(i + " is prime");
                sieves.add(new int[]{i*i,  i});
                count--;
            }
        }
    }
}

 

[discere]

Hallo, ich überprüfe, das Ergebnis ist nichtig. Anzahl ist teilweise falsch. a = 3;2; das ergebnis kommt nur ein Ergebnis raus.

und ein Frage: Was bedeutet ? Warum mit log??

do {
n *= 2;
q=(int) (n/Math.log(n)*1.1);
} while (q < gesuchteAnzahl);
return n;
}

Kannst du mir erklären??? Danke

Also ich bin mal nahe an dem Algo "Sieb des Eratosthenes" von Wikipedia geblieben.
Eingeflickt hab ich ne Abschätzung des Suchbereichs die man sicher optimieren könnte.
Primzahlsatz ? Wikipedia
Woher N = a*15 kommt, weiss ich nicht.
Dazu gekommen ist da dann auch der Zähler z, um die Suche dann zu beenden,
wenn die gewünschte Zahl an Primzahlen ausgegeben wurde.

public class PrimeJava {
	// Sieb des Eratosthenes 
	 
    public static void main(String[] args) {
        
        int a= Integer.parseInt(args [0]); //Anzahl der Primzahlen
        int n = getPrimeSearchLimit(a);
        int z=0;
        boolean[] gestrichen = new boolean[n-1];
        
        for (int i = 2; i <= n; i++) {
        	gestrichen[i-2] = false;	
        }
        
        for(int i=2; i <= n; i++) {
            if (!gestrichen[i-2]) {
                z++;
                System.out.println(i+ " ist Primzahl "+z);
                if (z==a) break;
            	for (int j = i*i; j <= n; j+=i) gestrichen[j-2]=true;
            }
        }
    }
    private static int getPrimeSearchLimit(int gesuchteAnzahl){
    	// Abschätzung des Suchbereiches für eine bestimmte Anzahl von Primzahlen
    	int n=1;
    	int q=1;
    	do {
    		n *= 2;
        	q=(int) (n/Math.log(n)*1.1);
    	} while (q < gesuchteAnzahl);
    	return n;    			
    }
}

 

[pappawinni]

Woher das kommt.. dazu hatte ich ja einen Link gesetzt.
Für die Abschätzung der bis zu einem bestimmten Wert x auftretenden Primzahlen a gibt es verschiedene Formeln.
a = x/ln(x) kommt dem relativ nahe. (Lesen was ich verlinkt habe, dafür mach ich das.)
Im Bereich von kleinen x liefert das aber zu niedrige Werte für a, für große x dann aber zu große Werte.
Leider hab ich es nicht geschaft die Formel a = x/ln(x) nach x aufzulösen,
deshalb verdopple ich x so lange, bis a hinreichend groß ist.
Dass du jetzt ausgerechnet ein Programm brauchst, mit dem du die ersten 3 Primzahlen ermitteln willst.. ok..
Es soll auch da funktionieren, ist ja gut....
ok...mit

q=(int) (n/Math.log(n)*0.9);

dürftest du auf der sicheren Seite sein...

Und wenn du mal 1 Mio. Primzahlen wissen willst, braucht es noch eine Absicherung, dass i*i nicht zum Überlauf führt.

public class PrimeJava {
	// Sieb des Eratosthenes 
	 
    public static void main(String[] args) {
        
        int a= Integer.parseInt(args [0]); //Anzahl der Primzahlen
        int n = getPrimeSearchLimit(a);
        int z=0;
        boolean[] gestrichen = new boolean[n-1];
        
        for (int i = 2; i <= n; i++) {
        	gestrichen[i-2] = false;	
        }
        
        for(int i=2; i <= n; i++) {
            if (!gestrichen[i-2]) {
                z++;
                System.out.println(i+ " ist Primzahl "+z+" n "+n);
                if (z==a) break;
                if (i <= Math.sqrt(n)) {
                	for (int j = i*i; j <= n; j+=i) {
                		if (j <= n) gestrichen[j-2]=true;
                	}                	                	
                }
            }
        }
    }
    private static int getPrimeSearchLimit(int gesuchteAnzahl){
    	// Abschätzung des Suchbereiches für eine bestimmte Anzahl von Primzahlen
    	int n=1;
    	int q=1;
    	do {
    		n *= 2;
        	q=(int) (n/Math.log(n)*0.9);
    	} while (q < gesuchteAnzahl);
    	return n;    			
    }
}

Du musst das aber nicht so machen...
könntest z.B. auch Legendre

        	q=(int) (n/(Math.log(n)-1.08366));

benutzen und die Iterationsmethode verbessern.

Selbst denken schadet im Allgemeinen nicht.

 

[pappawinni]

Also ich hab jetzt mal

getPrimeSearchLimit()

optimiert.
Jetzt kann sich jemand ein Fleissbienchen verdienen, der mal überprüft,
ob das irgendwo noch einen zu kleinen Suchbereich liefert.

    private static int getPrimeSearchLimit(int gesuchteAnzahl){
    	// Abschätzung des Suchbereiches für eine bestimmte Anzahl von Primzahlen
    	int n=2;
    	int q=1;
    	do {
    		n=(int) (n+(gesuchteAnzahl-q)*Math.log(n+1));
        	q=(int) (n/Math.log(n));
    	} while (q < gesuchteAnzahl);
    	return n;    			
    }