Subato

Sieve in C++

Die folgende Methode wird als “Sieb des Erathostenes” bezeichnet. Sie bestimmt alle Primzahlen unterhalb einer gegebenen Grenze n:

 

PROCEDURE SIEB(n)

  1. Schreibe alle Zahlen von 2 bis n nacheinander auf.
  2. Markiere die Zahl 2 als Primzahl und streiche alle Vielfachen der 2.
  3. Finde die kleinste nicht gestrichene und nicht markierte Zahl m.
  4. Markiere m als Primzahl und streiche alle Vielfachen von m.
  5. Führe die Schritte 3-4 solange aus, bis keine Zahl m ≤ n mehr gefunden wird.
  6. Alle markierten Zahlen sind Primzahlen.
Implementrieren Sie folgende Methoden:
  • boolean[] sieve(int n):
    Diese soll ein Boolesches Array b der Länge n + 1 zurückliefern, das für jede Zahl k = 0, ..., n anzeigt ob es sich um eine Primzahl handelt (b[k]) ob nicht (!b[k]).
  • List<Integer> primesUpTo(int n):
    Es soll eine Liste aller Primzahlen kleiner n erzeugt werden.
  • int[] primeFactors(int n):
    Sie soll für eine Zahl n den Array aller Primzahlen, die als Teiler in n vorkommen, erzeugen. Gegeben z.B. die Zahl 380 = 2 * 2 * 5 * 19, sollte die Methode das Array {2, 5, 19} zurückliefern. Die Primfaktoren sollen aufsteigend sortiert sein, und jeder soll nur einmal angegeben werden.

#include "sieve.h" #include <list> #include <stdlib.h> bool* sieve(int n) { bool *result = (bool*)malloc (sizeof(bool)*(n + 1)); return result; } std::list<int> primesUpTo(int n){ std::list<int> result = {}; return result; } int* primeFactors(int n) { int number = 0; int* result = (int*)malloc(sizeof(int)*number); return result; }
cc