Algorithmensammlung: Zahlentheorie: Sieb des Eratosthenes – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher (2024)

> module Sieve> where > sieb :: [Int] -> [Int]> sieb (l:ls) = l:sieb[x | x <- ls, mod x l /= 0]> take_primes n = take n $ sieb [2..]

# hugs Sieveoder für eine schnellere Version# ghc -O2 --make Sieve.lhs# ghci Sieve

Prelude Sieve> take_primes 100

using System;using System.Collections.Generic;using System.Text;namespace eratosthenes{ class Program { static void Main(string[] args) { int n = 100; bool[] prime = new bool[n]; //Zuerst alle Zahlen von 2 bis n als Primzahl markieren for (int i = 2; i < n; i++) { prime[i] = true; } //Einzelner Abschnitt { //Wir wollen bei 2 anfangen int i = 2; //Alle Produkte des Teilers i //angefangen bei 2, bis kleiner n durchlaufen //Wenn n = 50, dann ist bei i = 7 Schluss, weil das Produkt = 49 ist for (; i * i < n; i++) { //Wenn die Zahl im Array als Primzahl markiert ist //Was bei den ersten beiden 2 und 3 definitiv der Fall ist if (prime[i]) { //Primzahl bis Wurzel(n) ausgeben Console.WriteLine(i); //Alle weiteren Produkte des Teilers i //angefangen beim Produkt i * i bis kleiner n durchlaufen //j wird mit i beim nächsten Durchlauf (Vielfaches) addiert for (int j = i * i; j < n; j += i) { //Dies kann unmöglich eine Primzahl sein //weil es ein Vielfaches von i ist. prime[j] = false; } } } //Alle Primzahlen ausgeben for (; i < n; i++) { if (prime[i]) { Console.WriteLine(i); } } }  Console.ReadLine(); } }}

program Primzahl;{$APPTYPE CONSOLE}uses SysUtils;function IsPrim(AInteger: Integer): boolean;var i: Integer;begin result := true; if (AInteger <= 1) then //Wenn Zahl kleiner ist als 2: keine Primzahl begin result := false; exit; //Funktion beenden end; for i := 2 to Round(Sqrt(AInteger)) do //Wenn eine Zahl n von 2 bis Wurzel(n) begin // nicht teilbar ist, ist sie eine Primzahl if AInteger mod i = 0 then //mod: Modulo = Rest begin result := false; exit; end; end;end;var a, b: Integer; i: Integer;begin Write('von: '); Readln(a); //a abfragen Write('bis: '); Readln(b); //b abfragen for i := a to b do if IsPrim (i) then Writeln(i); //wenn i eine Primzahl ist: i ausgeben Readln;end.

#!/usr/bin/env python# -*- coding: utf-8 -*-def main(): # Frage den Benutzer nach einer Obergrenze bis zu der gesucht werden soll while True: try: obergrenze = int(raw_input('Bitte geben Sie eine Obergrenze ein: ')) break except ValueError: print 'Dies ist keine gültige Obergrenze. Bitte verwenden Sie eine Ganzzahl!' # Jede Zahl zwischen 1 und obergrenze wird zuerst als prim angenommen zahlen = [True]*(obergrenze+1) # Da 0 und 1 keine Primzahlen sind, werden sie auf False gesetzt zahlen[0] = False zahlen[1] = False i = 2 while i*i <= obergrenze: if zahlen[i]: # Die Zahl i ist als prim markiert # Streiche alle Vielfachen von i for k in range(i*i,obergrenze+1,i): zahlen[k] = False i = i+1 # Ausgabe aller gefundenen Zahlen for i, v in enumerate(zahlen): if v: print i, 'ist prim.' return 0if __name__ == '__main__': main()

#!/usr/bin/env python# -*- coding: utf-8 -*-# Python 3# Frage den Benutzer nach einer Obergrenze bis zu der gesucht werden sollwhile True: try: obergrenze = int(input('Bitte geben Sie eine Obergrenze ein: ')) break except ValueError: print ('Dies ist keine gültige Obergrenze. Bitte verwenden Sie eine Ganzzahl!')print (2)noprime = set()for n in range (3, obergrenze+1, 2): if n not in noprime: print (n) # alle ungeraden Vielfachen von n von n*n bis Obergrenze in ein set aufnehmen: for i in range(n*n, obergrenze+1, 2*n): noprime.add(i) else: noprime.discard(n) # wird nicht mehr gebraucht; dieser Schritt kann auch weggelassen werden

#include<iostream>#include<cmath>using namespace std; int main(void){ unsigned limit;  cout << "Please insert upper limit.\n"; cin >> limit;  bool *Stroke = new bool[limit+1]; Stroke[0]=1; Stroke[1]=1; for(unsigned i=2; i<=limit; ++i) Stroke[i] = 0;  unsigned prime=2; while(pow((double)prime,2.0)<=limit){ for(unsigned i = (int)pow((double)prime,2.0); i<=limit; i+=prime){ Stroke[i]=1; }  do ++prime; while(Stroke[prime]); }  cout << "\nPrimes less or equal " << limit << " are:\n"; for(unsigned i=0; i<=limit; ++i){ if(!Stroke[i]) cout << i << endl; } delete[] Stroke; return 0;}

#include <iostream>#include <iterator>#include <vector>#include <algorithm>#include <numeric>using namespace std;vector<unsigned> primes_upto(unsigned limit){ vector<unsigned> candidates(limit - 1); iota(begin(candidates), end(candidates), 2); // candidates = 2, 3, ..., n auto const upper_limit = (limit + 1) / 2; // ceil(limit/2) for (auto candidate = begin(candidates); // vector<unsigned>::iterator *candidate <= upper_limit; ++candidate) { auto const p = *candidate;  // 'erase-remove idiom': // remove_if(...) moves all multiples of p to the end and returns // an iterator to the beginning of the (re)moved part; // candidates.erase(..., end(candidates)) actually deletes these values candidates.erase(remove_if(candidate + 1, // don't remove p itself end(candidates), [p](auto q){ // capture p by value return (q % p == 0); }), end(candidates)); } return candidates; // copy elision guaranteed by C++ standard}int main(){ unsigned limit;  cout << "Please insert upper limit.\n"; cin >> limit; auto primes = primes_upto(limit); for (auto p : primes) cout << p << " "; cout << endl;}

sieb<-function(limit){ (vek<-2:limit)[1==apply(0==outer(vek, vek, "%%"), 1, sum)] # Primzahlen bis limit # %% Division mit Rest oder modulo}

package mainimport "math"func main () {var limit uint = 1000var zahl, zaehler uintvar primzahl boolfor zahl = 2; zahl <= limit; zahl++ {primzahl = truefor zaehler = 2; zaehler <= zahl/2; zaehler++ {if math.Mod(float64(zahl), float64(zaehler)) == 0 {primzahl = falsebreak}}if primzahl == true {println(zahl, " ist eine Primzahl")}}}