[HaBo]

Stein · 30.03.07, 21:43

Ein wunderschönes Ausgabelayout habe ich nicht, aber es klappt ganz gut wenn man denn genung RAM hat, wenn nicht muss man alles in MYSQL Tabellen anstatt von Array speichern. Hier das ganz in PHP:

PHP-Code:

  <?php
/*Das Sieb des Aristotoes:
"Man muss nicht rechnen können um Primzahlen zufinden nur zählen." Normaler Weiser schreibt man alle Zahlen auf ein Blatt und fängt bei 2 an: 2
 wir nicht durchgestrichen, zwei weiter (4) wird durch gestrichen usw. dann mit 3.*/

$zahlen = array(0);//Beginn der Berechnung
for ($i=1;$i<10000;$i++){
    $zahlen[$i] =1;
}
for($j=2;2*$j<10000;$j++){//"siebt" alle Zahlen bis zu Hälfte
    if ($zahlen[$j] == 1){//nur Vielfach von Primzahlen werden druchgestrichen wenn 
        for($k=$j;$k<10000;){ //ich alle Vielfach von 2 habe brauche ich die von 4 nicht.
            $k=$k+$j;
            $zahlen[$k] = 0;//Vielfach sind keine Primzahlen
        }
    }        
}    //Ende der Berechnung
//Beginn der Ausgabe
$primzahl = array(0);
for($l=1;$l<10000;$l++){
    if($zahlen[$l]==1){
        echo $l."<br>";
        $primzahlen[]= $l;//Menge aller Primzahlen
    }
}
//Jetzt die Primzahlpaarerweiterung:
echo "Primzahlpaare sind:<br>";
for($m=1;$m<count($primzahlen);$m++){
    if ($primzahlen[$m+1]-$primzahlen[$m] == 2){
        $mpluseins = $m +1;
        echo "$primzahlen[$m] | $primzahlen[$mpluseins] <br>";//mit [$m+1] hat leider nicht geklappt
    }
}
?>

my2$/100 · 08.04.07, 22:37

Es sieht fast aus wie C++. Ich habe es auch ursprünglich damit geschrieben. Die Eingabe ist aber viel robuster.

Die vorgehensweise ist naiv. Die einzigen Optimierungen sind:

Prüfung nur bis Wurzel(n)
gerade Teiler und gerade (Prim-)Zahlen werden ignoriert

Code:

import std.stream;
import std.math;
import std.stdio;
import std.string;

void eingabe(out uint min, out uint max)
{
    char input[6];
    do
    {
        writef("Untere Grenze: ");
        scanf("%s", &input);
        min = cast(uint) atoi(input);
        writef("Obere Grenze: ");
        scanf("%s", &input);
        max = cast(uint) atoi(input);
    }
    while(min<3 || max<=min);
}

bit isPrime(uint zahl)
{
    // Teiler bis wurzel(zahl) auf glatte Teilung prüfen
    // alle Vielefache von 2 können ignoriert werden
    uint grenze = cast(uint) sqrt(cast(real)zahl);

    for(uint i=3; i<=grenze; i+=2)
    {
        if(zahl%i==0)
           return false;
    }
    return true;
}

int main(char[][] args)
{
    bit last_was_prime = false;
    uint min,max;

    // Bereich eingeben
    eingabe(min,max);

    // Alle ungeraden Zahlen im Bereich prüfen
    // Bei der ersten ungeraden anangen
    for(uint i = min%2==0 ? min+1:min; i<=max; i+=2)
    {
        if(isPrime(i))
        {
            if(last_was_prime)
                writefln("%5d\t%5d", i-2, i);

            last_was_prime = true;
        }
        else
        {
            last_was_prime = false;
        }
    }
    return 0;
}

War mein erster D Test.

Ook! · 21.05.08, 02:39

Meine Groovy-Lösung

Code:

List doIt(start, end){
	couples = []
	
	for(i in start..end)
		if(isPrim(i) && isPrim(i+2))
			couples.add(i +" "+ (i+2))
	return couples
}

Boolean isPrim(num){
	for(x=2; x<=Math.sqrt(num); x++){
		if(num%x == 0)
			return false
	}
	return true
}

println doIt(3, 50) // 3 - 5, 5 - 7, 11 - 13, 17 - 19, 29 - 31, 41 - 43

Eine weitere Groovy-Variante... meiner Meinung nach sehr elegant

Code:

def doIt(start, end){
	return (start..end).findAll { n -> (start..<n).every { z -> n%z != 0 && (n+2)%z != 0 } }
}

doIt(3, 50).each { n -> print "${n} - ${n+2}, " } // 3 - 5, 5 - 7, 11 - 13, 17 - 19, 29 - 31, 41 - 43

Gruß
Felix

EDIT
Hier noch eine sehr schöne Scala Variante:

Code:

object PrimeNumbers extends Application {
  def isPrime(n : Int) : Boolean =
    List.range(2, n-1).filter(n%_ == 0).length == 0

  var list = List.range(3,50).filter(n => isPrime(n) && isPrime(n+2))
  list.foreach(n => println(n +" - "+ (n+2)))
}

pytohn · 14.04.09, 14:40

Hier eine Lösung in Python 3:

Code:

from math import *

def primzahl(x):
prim = True
for t in range(2, (x-1)):
if x/t == x//t:
prim = False
break
if prim == False or x == 1:
return False
else:
return True

try:
start = input("Startwert: ")
ende = input("Endwert: ")
start, ende = int(start), int(ende)
for i in range(start, (ende-2)):
if primzahl(i):
if primzahl(i+2):
output = "%d t %d" %(i, (i+2))
print(output)

except:
print("Leider trat ein Fehler auf!")

Eggmanne · 02.05.09, 15:46

Code:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  unsigned int number=7;                  //zu überprüfende,incrementirende zahl
  unsigned int i=3;                       
  unsigned short int counter=4;           //zählt die menge der primzahlen
  unsigned int last_prime=5;                    
  
//die ersten primzahlen werden geschenkt

  printf("%d , %d\n",3,5);
  for(;counter<=50;number+=2){
    for(i=3;number%i!=0 && i<=number/2;i+=2){   
    }

//wenn for schleife komplett durchgelaufen ist,
//also i>=number/2 dann ist number== prim   

    if(i>=number/2){        
      if(number==(last_prime+2))
        printf("%u , %u\n",last_prime,number);
      counter++;
      last_prime=number;
    }
  }
  
  getch();	
  return 0;
}

und noch ne schnelle c lösung

Stein · 03.05.09, 15:34

Da ich einiges an Langeweile hatte und sowie so Scheme üben muss:

Code:

(define (is_prim n teiler)
  (cond ((>(* teiler teiler) n) #t)
        ((= (remainder n teiler)  0) #f)
        (else (is_prim n (+ teiler 1)))))
(define (main n  end)
  (if (<= n end )(and
      (if (and (is_prim n 2) (is_prim (+ n 2) 2))
      (and (write n) (write "+")(write (+ n 2)) (write "-->")))
      (main (+ n 2) end))))

Damit habe ich wohl das kürzeste

edit:

Code:

(define (is_prim n teiler)  (cond ((>(* teiler teiler) n) #t)   ((= (remainder n teiler)  0) #f)   (else is_prim n (+ teiler 1))))) (define (main n  end)  (if (<= n end )(and     (if (and (is_prim n 2) (is_prim (+ n 2) 2))   (and (write n) (write "+")(write (+ n 2)) (write "-->"))) (main (+ n 2) end))))

Lesco · 03.05.09, 18:19

Zitat:

Original von Stein
Damit habe ich wohl das kürzeste

Die gepostete Groovy- und die Scala-Variante ist kürzer.

Hier nochmal eine Lösung in Haskell mit besserem Primzahlsieb(nur durch Primzahlen teilen):

Code:

isPrime x = all ((/=0) . (x `mod`)) . takeWhile ((<=x) . (^2)) $ primes

primes = 2:[x | x <- [3,5..], isPrime x]

paare n m = map (\x -> (x,x+2)) $ filter ((`elem` ps) . (+2)) ps
    where ps = takeWhile (<=m-2) . dropWhile (<=n) $ primes

**CDW** · 04.05.09, 12:07

Prolog mit einem Sieb:

Code:

notprim(N,E):-E=\=N, mod(E,N)=:=0.
primlist([],[]).
primlist([E|T],[E|R]):- exclude(notprim(E),T,ExList), primlist(ExList,R),!.

filter(_,[_]).
filter(Min,[E,E2|T]):- (E>=Min,2 is E2-E,writeln(E-E2),true),filter(Min,[E2|T]),!.
paare(From,To):-numlist(2,To,List),primlist(List,Prims),filter(From,Prims).

bzw. "größenoptimiert" (aber weniger gut lesbar

)

Code:

notprim(N,E):-E=\=N, mod(E,N)=:=0.
primlist([],[]). primlist([E|T],[E|R]):- exclude(notprim(E),T,ExList), primlist(ExList,R),!.
filter(Min,[E,E2|T]):- (E>=Min,E2-E=:=2 -> writeln(E-E2);true),filter(Min,[E2|T]),!.
paare(From,To):-numlist(2,To,List),primlist(List,Prims),filter(From,Prims).

Ausgabe:

Zitat:

?- paare(1,30).
3-5
5-7
11-13
17-19
fail.

pytohn · 02.11.09, 14:02

Hier noch eine Schemelösung:

Code:

(define primzahl
  (lambda (n t)
    (if (> n 1)
        (if (and (>= t 2) (< t n))
            (if (= (modulo n t) 0)
                #f
                (primzahl n (+ t 1)))
            #t)
        #f)))

(define paare
  (lambda (min max)
    (if (<= (+ min 2) max)
        (if (primzahl min 2)
            (if (primzahl (+ min 2) 2)
                (begin (write min) (display "\t") (write (+ min 2)) (display "\n") (paare (+ min 1) max))
                (paare (+ min 1) max))
            (paare (+ min 1) max))
        (display "Ende erreicht!"))))

; Beispiel-Aufruf (Paare von 1 bis 30):
; (paare 1 30)

Wenn ihr noch Tipps habt, wie ich das Programm verbessern kann, bitte eine PN schicken. Ich fange gerade erst mit Scheme an.

Chris_XY · 13.12.09, 23:13

Auch noch einmal von mir in Ada.

Eigentlich wollte ich ja auch das Sieb des Erastosthenes nutzen, aber als ich dann gesehen habe, dass man in Ada keine Schrittweite für For-Schleifen angeben kann, hatte ich da auch keine Lust mehr. Deshalb mit recht ineffizienter Primzahlbestimmung (Prüfen auf Rest = 0 für Ungerade Teiler bis Zahl/2). Am Ende ist aber immer noch die Ausgabe das langsamste.

Code:

with Ada.Text_IO, Ada.Integer_Text_IO;

procedure Primzahlpaare is
   Eingabe : Positive;

   function Ist_Paar (Zahl1, Zahl2 : Positive) return Boolean is
   begin
      if Zahl1 mod 2 /= 0 then
         for Zaehler in 3 .. Zahl1 / 2 loop
            if Zahl1 mod Zaehler = 0 or Zahl2 mod Zaehler = 0 then
               return False;
            end if;
         end loop;
      end if;
      return True;
   end Ist_Paar;

   procedure Paare_Ausgeben (Eingabe : Positive) is
   begin
      for Zaehler in 3 .. Eingabe loop
         if Zaehler mod 2 /= 0 then
            if Ist_Paar (Zaehler, Zaehler + 2) then
               Ada.Integer_Text_IO.Put (Zaehler, 1);
               Ada.Text_IO.Put (" - ");
               Ada.Integer_Text_IO.Put (Zaehler + 2, 1);
               Ada.Text_IO.New_Line;
            end if;
         end if;
      end loop;
   end Paare_Ausgeben;

begin
   Ada.Text_IO.Put ("Obere Grenze eingeben (positive Zahl): ");
   Ada.Integer_Text_IO.Get (Eingabe);
   Ada.Text_IO.Put_Line ("Primzahlpaare: ");
   Paare_Ausgeben (Eingabe);
end Primzahlpaare;

goflo · 14.01.10, 19:36

Es sind ja Lösungen in fast allen Sprachen vorhanden, aber eine VBA Lösung hab ich nicht gesehen.

Code:

Option Explicit

Sub PrimePairGenerator()
    Dim start As Integer, ende  As Integer
    Dim i As Integer, row As Integer
    
    start = Sheets("Tabelle1").Range("E1")
    ende = Sheets("Tabelle1").Range("E2")
    row = 1
    
    Columns("A:B").ClearContents
    
    If start <= 2 Then start = 3
    
    For i = start To ende Step 2
        If isPrime(i) = True And isPrime(i + 2) = True Then
            Sheets("Tabelle1").Cells(row, 1) = i
            Sheets("Tabelle1").Cells(row, 2) = i + 2
            row = row + 1
        End If
    Next i
    
End Sub

Function isPrime(nb As Integer) As Boolean
    Dim i As Integer
    
    If nb Mod 2 = 0 Then
        isPrime = False
        Exit Function
    End If
    
    For i = 3 To (nb/2) Step 2
        If nb Mod i = 0 Then
            isPrime = False
            Exit Function
        End If
    Next i
    
    isPrime = True
End Function

pytohn · 28.02.10, 18:22

Fange gerade an, Perl zu lernen, also hier in Perl:

Code:

print "Anfangswert:\t";
$start = <STDIN>;
print "Endwert:\t";
$ende = <STDIN>;

foreach $x ($start..$ende-2) {
        if (ist_primzahl($x) and ist_primzahl($x+2)) {
                print $x, "\t", $x+2, "\n";
        }
}

sub ist_primzahl {
        my($zahl) = @_;
        if ($zahl eq 1) {
                $prim = 0;
        }
        else {
                $prim = 1;
        }
        foreach $teiler (2..sqrt ($zahl)) {     # nur bis zur Wurzel von $zahl
                if ( ($zahl % $teiler) eq 0) {   # Modulo-Test
                        $prim = 0;      # Keine Primzahl: => falsch
                }
        }
        if ($prim eq 1) {
                return 1;       # Ist eine Primzahl: => wahr
        }
        else {
                return 0;       # Ist keine Primzahl:=> falsch
        }
}

pytohn · 02.04.10, 13:07

Habe meine alte Perlversion ein bisschen aufgewertet:

Code:

print "Anfangswert:\t";
$start = <STDIN>;
print "Endwert:\t";
$ende = <STDIN>;

foreach $x ($start..$ende-2) {
        if (ist_primzahl($x) and ist_primzahl($x+2)) {
                print $x, "\t", $x+2, "\n";
        }
}

sub ist_primzahl {
        my($zahl) = @_;
        if ($zahl eq 1) {
                return 0;
        }
        foreach $teiler (2..sqrt ($zahl)) {     # nur bis zur Wurzel von $zahl
                if ( ($zahl % $teiler) eq 0) {  # Modulo-Test
                        return 0;       # Keine Primzahl: => falsch
                }
        }
        return 1;
}

DMRMcK · 23.12.10, 15:13

Eine Möglichkeit in VB.

VB-Code

NattleBet · 08.06.11, 09:04

JAVA

Empfehlung

30.03.07, 21:43	#16 (permalink)
Stein Registriert seit: 10.10.05 Likes: 0	Ein wunderschönes Ausgabelayout habe ich nicht, aber es klappt ganz gut wenn man denn genung RAM hat, wenn nicht muss man alles in MYSQL Tabellen anstatt von Array speichern. Hier das ganz in PHP: PHP-Code: <?php /Das Sieb des Aristotoes: "Man muss nicht rechnen können um Primzahlen zufinden nur zählen." Normaler Weiser schreibt man alle Zahlen auf ein Blatt und fängt bei 2 an: 2 wir nicht durchgestrichen, zwei weiter (4) wird durch gestrichen usw. dann mit 3./ $zahlen = array(0);//Beginn der Berechnung for ($i=1;$i<10000;$i++){ $zahlen[$i] =1; } for($j=2;2*$j<10000;$j++){//"siebt" alle Zahlen bis zu Hälfte if ($zahlen[$j] == 1){//nur Vielfach von Primzahlen werden druchgestrichen wenn for($k=$j;$k<10000;){ //ich alle Vielfach von 2 habe brauche ich die von 4 nicht. $k=$k+$j; $zahlen[$k] = 0;//Vielfach sind keine Primzahlen } } } //Ende der Berechnung //Beginn der Ausgabe $primzahl = array(0); for($l=1;$l<10000;$l++){ if($zahlen[$l]==1){ echo $l."<br>"; $primzahlen[]= $l;//Menge aller Primzahlen } } //Jetzt die Primzahlpaarerweiterung: echo "Primzahlpaare sind:<br>"; for($m=1;$m<count($primzahlen);$m++){ if ($primzahlen[$m+1]-$primzahlen[$m] == 2){ $mpluseins = $m +1; echo "$primzahlen[$m] \| $primzahlen[$mpluseins] <br>";//mit [$m+1] hat leider nicht geklappt } } ?> __________________ Steinhagelvoll

08.06.11, 09:04	#30 (permalink)
NattleBet Registriert seit: 07.06.11 Likes: 0	JAVA public class Primzahlenpaar { private boolean isPrim(int number) { if (number <= 1) return false; for (int i = 2; i < number; i++) if (number % i == 0) return false; return true; } private void next(int i) { if (isPrim(i)) if (isPrim(i + 2)) System.out.println(i + " - " + (i + 2)); } public static void main(String[] args) { int endwert = 30; Primzahlenpaar prim = new Primzahlenpaar(); for (int i = 1; i <= endwert - 2; i++) prim.next(i); } } Geändert von NattleBet (08.06.11 um 09:06 Uhr)

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Mathe Aufgabe	Nimda05	Science & Fiction	10	26.08.08 11:58
UNI Aufgabe	Kaya	Code Kitchen	19	05.04.07 19:16
Aufgabe	daddycool	Code Kitchen	5	13.01.06 08:28
Aufgabe	poldi	Code Kitchen	2	14.01.04 18:02

[HaBo]

Aufgabe Nr. 1: Primzahlenpaare