Primzahlen bis 1000000

A

Anfänger22

Aktives Mitglied
Ich bin ein Anfänger und möchte mich weiterbilden...leider komm ich bei dieser aufgabe nicht vorbei...
wäre jemand so nett, mir die Aufgabe so leicht wie möglich zu schreiben...will des einfach mal verstehen...selber komme ich nicht mehr weiter


Schreiben Sie ein Programm, das alle Primzahlen bis 1 000 000 berechnet.
Das Programm soll leicht auf andere Höchstzahlen änderbar sein.
Sieb des Eratosthenes:
Zuerst alle geraden Zahlen (bis auf 2) streichen, dann alle Vielfachen von 3, usw. mit der jeweils nächsten Primzahl.
überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss.
Anmerkung: Man könnte das auch mit Nicht-Primzahlen machen (z.B. 4), dann streicht man aber nur Zahlen,
die vorher schon gestrichen worden sind.

Geben Sie zur Kontrolle die ersten 100 und die letzten 10 Primzahlen aus, immer 10 pro Zeile.
 
B

bygones

Gast
suchen ist schon schwierig...

allein bei google findet man zig einträge nur in diesem Forum dazu. Wenn du schon was hingekautes bekommen willst dann ists einfacher google zu nutzen.

die moralische Keule von wegen "weiterbilden" und dann nach fertigem zu fragen erspar ich mir....
 
A

Andi_CH

Top Contributor
Im Gegensatz zur Lottoziehung sind hier die Requirements SEHR präzise beschrieben - da ist ja sogar das Design schon gelöst.

Überlegung: 10^6 hat locker in einem int platz

Offene Frage - "überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss. " ist eine mathematische und hat nichts mit Java zu tun - du musst bis zur Wurzel des Primzahlenkandiaten streichen. (Falls du es wissen willst erkläre ich dir warum, aber kannst es auch einfach glauben.)

Die "Anmerkung" kannst du einfach vergessen - die bringt nichts.

So, wenn ich jetzt die Lösung auch nur ansatzweise hier reinkopiere hast du nichts gelernt.

(Übrigens: Programmieren beginnt immer auf einem "Papier" - ok, es kann auch ein office oder sonst was Dokument sein, aber den Kompiler braucht man erst später)
 
ARadauer

ARadauer

Top Contributor
Offene Frage - "überlegen Sie sich, mit welcher Zahl maximal gestrichen werden muss. " ist eine mathematische und hat nichts mit Java zu tun - du musst bis zur Wurzel des Primzahlenkandiaten streichen. (Falls du es wissen willst erkläre ich dir warum, aber kannst es auch einfach glauben.)
Zum Vergrößern anklicken....
Gibts leute die da warum fragen?
 
A

Anfänger22

Aktives Mitglied
wer will kann gerne helfen...wer nicht soll sich bitte daraushalten...das problem ist, dass ich bei dieser aufgabe nix versteh...hab mich an euch gewendet, damit ihr mir des mal erklärt.
ich flehe euch nicht an...ich hab nur höfflich gefragt ob ihr mir dabei helfen könnt....
die aufgabe steht oben...und ich würde mich freuen, wenn mir jemand die aufgabe mal lösen würde...danke
 
ARadauer

ARadauer

Top Contributor
Na was jetzt? Helfen oder lösen?
Das ist schon ein Unterschied. Beim helfen musst du auch was machen, biem Lösen poste ich nur die Lösung.

Also ich versuch mal zu helfen.
Beim Sieb des Eratosthenes geht man her und macht sich ein boolean array wo drinnen steht ob die Zahl eine Primzahl ist.

zb so

Java: 
int anzahl = 100;		
		boolean[] isPrim = new boolean[anzahl];
		
		if(isPrim[6]){
		   System.out.println("Ja ist ein Primzahl");
		}
wie der geübte mathematiker erkennen kann, fehlt her noch was... 6 ist gar keine primzahl...

also müssen wir alle nicht primzahlen streichen

alle die durch, 2 teilbar sind auf false, alle die durch 3 teilbar sind auf false, alle die durch 4 mhnn seltsam.. macht ja keinen sein, alle die durch 4 teilbar sind haben wir schon gestrichen... die warn ja schon durch 2 teilbar... mhn also wir nehmen nur 2, 3 und alle weiteren primzahlen. so das it der ansatz...

so wie setzen wir jetzt alle die druch 2,3, usw teilbar sind auf false... wir teilen nichit sondern setzen alle vielfachen auf false...

Java: 
i ist hier die zahl wo wir prüfen...
for(int j = i*i;j<anzahl; j+=i)					
   isPrim[j] = false;				
}

so ungefähr, aussen rum noch ne for schleife die muss aber nicht die ganzen prüfen.. nur bis zur wurzel.. is so.
dann noch das if(isPrim){ um das was ich schon gepostet habe und fertig...
 
Landei

Landei

Top Contributor
Man muss das array allerdings erst mal mit lauter trues initialisieren. Am einfachsten mit java.util.Array.fill
 
A

Anfänger22

Aktives Mitglied
Java: 
import java.io.*;

public class Primzahl {
  
  public static void main(String[] args) throws IOException {
    // bestimmt Primeigenschaft
    
    BufferedReader in = new BufferedReader(
                          new InputStreamReader(System.in));
    
    // Zahl erfragen
    String s;    // String für eingegebene Zeile
    System.out.println("Positive ganze Zahl eingeben:");
    s = in.readLine();
    int zahl = Integer.parseInt(s);
    
    boolean isPrim = true;  // bis zum Beweis des Gegenteils
    int teiler = 1;         // gefundener Teiler
    
    if (zahl % 2 == 0) { // durch 2 teilbar
      isPrim = false;
      teiler = 2;
    } else {
      int max = (int) Math.floor(Math.sqrt((double) zahl));
      for (int i=3; i<=max; i=i+2) {
        if (zahl % i == 0) {  // durch ungerade Zahl kleiner Wurzel teilbar
          isPrim = false;
          teiler = i;
        }
      }
    }
    
    // Ausgabe des Ergebnisses
    if (isPrim) {
      System.out.println(zahl + " ist eine Primzahl");
    } else {
      System.out.println(zahl + " ist durch " + teiler + " teilbar");
    }
  }
}
das wär jetzt die lösung ausm buch gewesen.
 
Zuletzt bearbeitet:
A

Anfänger22

Aktives Mitglied
Anfänger22 hat gesagt.:
Java: 
import java.io.*;

public class Primzahl {
  
  public static void main(String[] args) throws IOException {
    // bestimmt Primeigenschaft
    
    BufferedReader in = new BufferedReader(
                          new InputStreamReader(System.in));
    
    // Zahl erfragen
    String s;    // String für eingegebene Zeile
    System.out.println("Positive ganze Zahl eingeben:");
    s = in.readLine();
    int zahl = Integer.parseInt(s);
    
    boolean isPrim = true;  // bis zum Beweis des Gegenteils
    int teiler = 1;         // gefundener Teiler
    
    if (zahl % 2 == 0) { // durch 2 teilbar
      isPrim = false;
      teiler = 2;
    } else {
      int max = (int) Math.floor(Math.sqrt((double) zahl));
      for (int i=3; i<=max; i=i+2) {
        if (zahl % i == 0) {  // durch ungerade Zahl kleiner Wurzel teilbar
          isPrim = false;
          teiler = i;
        }
      }
    }
    
    // Ausgabe des Ergebnisses
    if (isPrim) {
      System.out.println(zahl + " ist eine Primzahl");
    } else {
      System.out.println(zahl + " ist durch " + teiler + " teilbar");
    }
  }
}
das wär jetzt die lösung ausm buch gewesen.
Zum Vergrößern anklicken....

aber kann man sich das leben auch einfacher machen und die lösung leichter machen???
bitte ganzes programm schreiben
 
ARadauer

ARadauer

Top Contributor
aber kann man sich das leben auch einfacher machen und die lösung leichter machen???
Zum Vergrößern anklicken....
ja das sieb des Eratosthenes anwenden. Warum fragst du eigentlich hier im Forum? Das ist ein Standard Beispiel, das schon von Millionen von Studenten gelöst wurde... alleine auf der ersten seite in google wenn ich nach "Eratosthenes java" suche finde ich 5 Lösungen?

naja ausnahmsweise...

Java: 
public class Sieb {	

	public static void main(String[] args) {
		
		int anzahl = 100;		
		boolean[] isPrim = new boolean[anzahl];
		
		//init
		for(int i = 0; i < isPrim.length; i++)
			isPrim[i] = true;
		
		//primzahlen berechnen
		int i = 2;
		while(i*i<anzahl){			
			if(isPrim[i]){				
				for(int j = i*i;j<anzahl; j+=i)					
					isPrim[j] = false;				
			}
			i++;
		}		
		
		//Ausgabe
		for(int k = 2; k < isPrim.length; k++){
			if(isPrim[k])
				System.out.print(k+", ");
			if((k % 100) == 0)
			   System.out.println();
		}
	}
}
am Ende vom Semester verzweifelst du sowieso....
 
ARadauer

ARadauer

Top Contributor
mhn ich versteh dich schon, das sieht alles sehr komplex aus und du denkst dir wenn du die lösung hast kannst du dir das ja anahnd des fertigen codes beibringen... aber glaubs mir.. das ist vollkommen falsch.

1. das ist ein ganz einfaches beispiel, das man schon mit papier und bleistift nachvollziehen kann, das sieht nur komliziert aus.
2. Durch das code lesen lernt man das programmieren nicht. Eigenen Code schreiben ist viel einfacher als fremden Code verstehen und man lernt dabei viel mehr.

es ist noch kein meister vom himmel gefallen....ich übe
Zum Vergrößern anklicken....
dazu sind ja solche Beispiele da... aber man muss sie selber machen, damit man das Basiswissen lernt.

Im Grunde hast du dir gerade die Konjugations Hausübung in Französch kopiert. Wenn nu nächstes Semster einen Aufsatz schreiben musst hast du keine Chance...
 

Aktuelle Jobs

Neue Themen


Oben