primzahlen bestimmen

buschimann

hallo!

ich soll ein programm schreiben, dass alle alle primzahlen von 3 bis 2100 berechnet und in einem vector<int> speichert.

allerdings habe ich noch etwas schwierigkeiten mit vektoren zu arbeiten.

int primzahl=3;

vector<int> primvektor;
prim.push_back(primzahl);

for (int i=3; i<=2100; i+=2)
{

for (int j=0; j<prim.size(); j++)
if(i%prim [j]!=0) { prim.push_back(i);}

sowas habe ich zur zeit, aber natürlich funktioniert das so nicht, denn i%prim [j] ist ja wieder ein vektor und ich kann damit nicht bestimmen, ob da ein glied 0 ist.
ihr merkt wohl, das mit dem programmieren ist alles noch relativ neu für mich^^

ich würde mich über eine kleine hilfe freuen.

pumuckl

zerleg dir das Problem:
erster Schritt:

std::vector<int> prim;
for (int i = 2; i <= 2100; ++i)
{
  if (/* i ist prim */)
  {
    prim.push_back(i);
  }
}

jetzt ist zu überlegen wie man rausfindet ob i prim ist.
Brute-force wäre, für alle Zahlen kleiner i die Teilbarkeit von i durch die jeweilige Zahl zu testen. Wird kein Teiler gefunden, dann ist i prim.
Es gibt aber zwei Verbesserungsmöglichkeiten:

wenn i Teiler hat, also gilt i = a*b, dann ist entweder a oder b kleiner oder gleich der Wurzel von i. Man muss also nur bis zur Wurzel nach Teilern suchen
wenn i Teiler hat, dann ist der kleinste Teiler von i eine Primzahl. Außerdem haben wir zu jedem gegebenen Zeitpunkt schon alle Primzahlen kleiner als i im vector gespeichert. wir müssen also nur alle Elemente im vector auf Teilbarkeit testen, die kleiner sind als die Wurzel von i.

also

std::vector<int> prim;
for (int i = 2; i <= 2100; ++i)
{
  //Teilbarkeit von i testen:
  bool isPrim = true;
  for (std::vector<int>::iterator it = prim.begin(), end = prim.end();
       it != end && (*it < std::sqrt(i)) ; //Reihenfolge ist wichtig!
       ++it)
  {
    if ((i % *it) == 0) //teiler gefunden?
    {
      isPrim = false;
      break;  //Schleife verlassen, brauchen nicht weiter suchen
    }
  }
  //entweder wurde die Schleife abgebrochen weil ein Teiler gefunden wurde, dann ist isPrim == false
  //oder sie ist bis zum Ende durchgelaufen und isPrim == true

  if (isPrim)
  {
    prim.push_back(i);
  }
}

Die Reihenfolge oben ist daher wichtig, weil it nur dann dereferenziert werden darf wenn it != end, hier wird also vom Kurzschluss-operator gebrauch gemacht.