Sieb des Eratosthenes < Java < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Implementieren Sie das Sieb des Eratosthenes, das alle Primzahlen bis zu einer vorgegebenen oberen Schranke n findet. Gehen Sie dazu wie folgt vor:
1. Geben Sie n ein und legen Sie eine Liste aller Zahlen von 2...n an.
2. Suchen Sie die nächste nichtmarkierte Zahl p in der Liste (zu Beginn ist p = 2).
3. Markieren Sie alle Vielfachen von p.
4. Gehen Sie zu 2. Falls kein p mehr vorhanden ist, geben Sie alle nichtmarkierten Zahlen (5 pro Zeile) aus (dies sind alles Primzahlen).
5. Geben Sie in der letzten Zeile (eine!) die Primzahlzerlegung von n in aufsteigender Reihenfolge aus (zur Formatierung siehe das Beispiel unten). Verwenden Sie dafür die Primzahlen aus dem Sieb.
Es gibt einfache Verbesserungen obiger Vorgangsweise, die Sie natürlich auch implementieren können.
Beispiel:
20
Ausgabe:
2 3 5 7 11 |
Hallo!
Meine Frage: und zwar wie bekomme ich das mit der Ausgabe hin damit mir nur 5 Zahlen augegeben werden?
Vielen Dank!
Hier mein Programm:
import java.util.*;
public class {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.println("Geben Sie eine ganze Zahl ein. ");
int eingabe;
eingabe = in.nextInt();
boolean[] markiert = new boolean[eingabe];
while (eingabe <= 1){
eingabe = in.nextInt();}
for (int i = 2; i < eingabe-1; i++){
markiert[i] = false;}
for (int i = 2; i <= eingabe-1; i++){
for(int j = 2; j < eingabe/2; j++){
for(int k = 2; k < eingabe/2 ; k++){
if(k*j < eingabe){
markiert[k*j] = true;
}
}
}
if (!markiert[i]){
System.out.print( i );
}
}
}
}
|
|
| |
|
moin,
Eine sehr bodenständige (und durchaus verbesserungsfähige^^) Variante wäre einfach einen Zähler einzufügen:
> import java.util.*;
>
>
> public class {
>
> public static void main(String[] args){
>
int counter;
> Scanner in = new Scanner(System.in);
> System.out.println("Geben Sie eine ganze Zahl ein.
> ");
> int eingabe;
> eingabe = in.nextInt();
> boolean[] markiert = new boolean[eingabe];
>
> while (eingabe <= 1){
>
> eingabe = in.nextInt();}
>
> for (int i = 2; i < eingabe-1; i++){
>
> markiert = false;}
>
>
> for (int i = 2; i <= eingabe-1; i++){
>
> for(int j = 2; j < eingabe/2; j++){
>
> for(int k = 2; k < eingabe/2 ; k++){
>
> if(k*j < eingabe){
>
> markiert[k*j] = true;
> }
> }
> }
> if (!markiert){
>
counter++;
> System.out.print( i ); if(counter==4) { System.out.println(""); counter = 0;}
> }
> }
> }
> }
lg
|
|
|
| |
|
Hallo!
Blödsinn !
Ich möchte jeweils in jeder Zeile fünf Primzahlen ausgeben!
Nicht mehr und nicht weniger!
Sorry!
Vielleicht weiß jemand wie sowas geht!
lg
|
|
|
| |
|
Hi!
Noch was:
Hier legst du dir ein boolean array an.
> boolean[] markiert = new boolean[eingabe];
Die einzelnen boolean speicherfelder werden von vornherein mit "false" deklariert.
Daher ist dein folgender Schritt unnötig.
> for (int i = 2; i < eingabe-1; i++){
>
> markiert = false;}
Valerie
|
|
|
| |
|
| Aufgabe | import java.util.Scanner;
public class Bsp0{
public static void main(String[] args) {
int eingabe = 0;
int counter = 0;
// Für die Eingabe von der Tastatur
Scanner in = new Scanner(System.in);
System.out.println("Geben Sie eine ganze Zahl ein, die größer als 1 ist. ");
// Eingabe, int-Wert einlesen
eingabe = in.nextInt();
boolean[] teilbar = new boolean[eingabe + 1];
// Alle Stellen des Arrays auf false setzen
//### < statt <=
for (int i = 2; i < teilbar.length; i++) {
teilbar[i] = false;
}
// Vielfache bilden und "wegstreichen"
for (int i = 2; i < teilbar.length; i++) {
while (teilbar[i]) { // suche nächste noch nicht als "teilbar" markierten zahl
i++;
}
for (int j = i; j*i < eingabe; j++) {
teilbar[i * j] = true;
}
if (! teilbar[i] && i < eingabe) {
counter++;
if(counter==5) { System.out.println("");}
System.out.println( i );
}
}
}
} |
Hallo nochmals!
Vielen Dank für die schnellen Antworten!
Wirklich Klasse!!!
Leider funktionierts noch immer nicht so ganz.
Ich möchte wenn ich die Zahl 20 eingebe nur die Primzahlen
2 3 5 7 11
in dieser Form ausgegeben bekommen.
Vielleicht kann mir jemand weiterhelfen?!?
Vielen Dank !!!
lg
|
|
|
| |
|
Hi!
| 1: | import java.util.Scanner;
| | 2: |
| | 3: | public class Bsp0{
| | 4: | public static void main(String[] args) {
| | 5: |
| | 6: |
| | 7: | int eingabe = 0;
| | 8: | int counter = 0;
| | 9: | int grenze = 5;
| | 10: | // Für die Eingabe von der Tastatur
| | 11: | Scanner in = new Scanner(System.in);
| | 12: |
| | 13: |
| | 14: | System.out.println("Geben Sie eine ganze Zahl ein, die größer als 1 ist. ");
| | 15: | // Eingabe, int-Wert einlesen
| | 16: | eingabe = in.nextInt();
| | 17: |
| | 18: | boolean[] teilbar = new boolean[eingabe + 1];
| | 19: |
| | 20: | // Alle Stellen des Arrays auf false setzen
| | 21: | //### < statt <=
| | 22: | for (int i = 2; i < teilbar.length; i++) {
| | 23: | teilbar[i] = false;
| | 24: |
| | 25: | }
| | 26: |
| | 27: | // Vielfache bilden und "wegstreichen"
| | 28: |
| | 29: | for (int i = 2; i < teilbar.length; i++) {
| | 30: |
| | 31: | while (teilbar[i]) { // suche nächste noch nicht als "teilbar" markierten zahl
| | 32: |
| | 33: | i++;
| | 34: | }
| | 35: |
| | 36: | for (int j = i; j*i < eingabe; j++) {
| | 37: | teilbar[i * j] = true;
| | 38: |
| | 39: | }
| | 40: |
| | 41: |
| | 42: | if (! teilbar[i] && i < eingabe) {
| | 43: |
| | 44: |
| | 45: | counter++;
| | 46: | if(counter > grenze){
| | 47: | break;
| | 48: | }
| | 49: | System.out.println( i );
| | 50: | }
| | 51: |
| | 52: | }
| | 53: | }
| | 54: | }
| | 55: |
|
Ich habe hier einfach eine neue Variable "Grenze" eingefügt. Wenn dein counter nun größer der Grenze ist, wird die Schleife verlassen.
Du hattest vorher einfach einen neuen Absatz begonnen, wenn n=5 war.
Um das Ganze in eine Zeile zu schreiben, solltest du nicht .println() verwenden, sonder nur .print(). Dazwischen noch ein paar leerzeichen, damit man die Zahlen auch auseinander halten kann.
Warum möchtest du diese Grenze überhaupt?
Wenn man die Eingabe macht, bestimmt man doch selbt die Grenze.
Wenn ich nicht so viele Primzahlen sehen möchte, setze ich die Eingabe einfach niedriger.
Die Zeilenvariante würde so aussehen:
| 1: |
| | 2: | import java.util.Scanner;
| | 3: |
| | 4: | public class Bsp0{
| | 5: | public static void main(String[] args) {
| | 6: |
| | 7: |
| | 8: | int eingabe = 0;
| | 9: | int counter = 0;
| | 10: | int grenze = 5;
| | 11: | // Für die Eingabe von der Tastatur
| | 12: | Scanner in = new Scanner(System.in);
| | 13: |
| | 14: |
| | 15: | System.out.println("Geben Sie eine ganze Zahl ein, die größer als 1 ist. ");
| | 16: | // Eingabe, int-Wert einlesen
| | 17: | eingabe = in.nextInt();
| | 18: |
| | 19: | boolean[] teilbar = new boolean[eingabe + 1];
| | 20: |
| | 21: | // Alle Stellen des Arrays auf false setzen
| | 22: | //### < statt <=
| | 23: | for (int i = 2; i < teilbar.length; i++) {
| | 24: | teilbar[i] = false;
| | 25: |
| | 26: | }
| | 27: |
| | 28: | // Vielfache bilden und "wegstreichen"
| | 29: |
| | 30: | for (int i = 2; i < teilbar.length; i++) {
| | 31: |
| | 32: | while (teilbar[i]) { // suche nächste noch nicht als "teilbar" markierten zahl
| | 33: |
| | 34: | i++;
| | 35: | }
| | 36: |
| | 37: | for (int j = i; j*i < eingabe; j++) {
| | 38: | teilbar[i * j] = true;
| | 39: |
| | 40: | }
| | 41: |
| | 42: |
| | 43: | if (! teilbar[i] && i < eingabe) {
| | 44: |
| | 45: |
| | 46: | counter++;
| | 47: | if(counter > grenze){
| | 48: | break;
| | 49: | }
| | 50: | System.out.print(i+" " );
| | 51: | }
| | 52: |
| | 53: | }
| | 54: | }
| | 55: | }
|
Valerie
|
|
|
|
