Aufgabe Nr. 1: Primzahlenpaare

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))))
 
Original von Stein
Damit habe ich wohl das kürzeste :)
Zum Vergrößern anklicken....

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
 
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:
?- paare(1,30).
3-5
5-7
11-13
17-19
fail.
Zum Vergrößern anklicken....
 
Scheme-Lösung

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.
 
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;
 
Es sind ja Lösungen in fast allen Sprachen vorhanden, aber eine VBA Lösung hab ich nicht gesehen. :wink:

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
 
Zuletzt bearbeitet:
Perl

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
        }
}
 
Perl verbessert

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;
}
 
Eine Möglichkeit in VB.

Code: 
Module Module1
    Public anfZahl As Integer
    Public endZahl As Integer
    Public zahlen(0) As Integer
    Public zaehler As Integer = 0

    Sub Main()
        Console.Write("Bitte den Anfangswert des Wertebereichs eingeben: ")
        anfZahl = Console.ReadLine
        Console.Write("Bitte den Endwert des Wertebereichs eingeben: ")
        endZahl = Console.ReadLine
        Console.WriteLine()

        Dim prim(endZahl + 1) As Boolean
        For i As Integer = 0 To endZahl + 1
            prim(i) = True
        Next
        For j As Integer = 2 To endZahl
            prim(j) = False
        Next

        primSuche(prim)

        For z As Integer = 0 To zahlen.Length - 2
            If zahlen(z) + 2 = zahlen(z + 1) Then
                Console.WriteLine(zahlen(z) & " - " & zahlen(z + 1))
            End If
        Next

        Console.ReadLine()
    End Sub

    Public Sub primSuche(ByRef prim() As Boolean)
        For i As Integer = 2 To endZahl
            If Not prim(i) Then
                ReDim Preserve zahlen(zaehler)
                zahlen(zaehler) = i
                zaehler += 1
                For j As Integer = i * i To endZahl Step i
                    prim(j) = True
                Next
            End If
        Next
    End Sub

End Module
 
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);
}
}
 
Zuletzt bearbeitet:
Hey

nachdem ich hier die Lösungen angeschaut habe, gehen die meisten hier nach folgendem Schema vor:

Man bekommt n, geht von 1 bis n durch, wobei man überprüft ob i und i+2 Primzahlen sind. Natürlich erreicht man dadurch das Ziel, meiner Meinung nach aber nicht effektiv genug. Deswegen hab ich auch mal einen Algorithmus dafür entworfen:

Code: 
public class primpaar {

	public primpaar(int n){
		
		boolean prims[] = new boolean[n + 1];
		
		for(int i = 0; i <= n; i++){
			
			prims[i] = true;
			
		}
		
		prims[0] = false;
		prims[1] = false;
		
		for(int i = 2; i <= Math.sqrt(n); i++){
			
			for(int k = n/i; k >= i; k--){
				
				prims[i*k] = false;
				
			}
			
		}
		
		for(int i = 0; i <= n-2; i++){
			
			if(prims[i] && prims[i+2]){
				
				System.out.println("Primzahlpaar: " + i + " | " + (i+2));
				
			}
			
		}
		
	}

}

Mein Schema: Erzeuge eine Liste von Primzahlen bis n, schaue, ob dort ein Primzahlpaar drinnen liegt.

Grüße

Scutus
 
Erster Beitrag

Hi Leute

hatte gerade nix zu tun und hab mich mal an der Aufgabe versucht;)

ich programmiere zwar schon seit 5 Jahren aber erst seit nem halben Jahr mit c++

Falls ich was besser machen könnte könnt ihr mich gerne berichtigen:)

MfG

Python-Fx

hier der Code:
Code: 
#include <iostream>
 
using namespace std;
 
bool isPrim(int n){
 
 if(n == 0)
  return false;
 
 for (int i = 2; i<  n; i++){
 
  if ( ( (n % i) == 0) && (i != n) && (i != 1) )
   return false;
 };
 
 return true;
 
};
 
 
int main(){
 
 int start, end, pim[2];
 
 prim[0] = 0;
 prim[1] = 0;
 
 cout << "START: ";
 cin >> start;
 cout << "END: ";
 cin >> end;
 cout << endl;
 
 for (int i = start; i <= end; i++){
 
  if (isPrim(i) == true){
 
   if(prim[0] == 0){
    prim[0] = i;}
   else prim[1] = i;
 
   if ( (prim[0] != 0) && (prim[1] != 0) ){
 
    if( (prim[1] - prim[0]) == 2){
     cout << prim[0] << " - " << prim[1] << "\n";
    };
    prim[0] = prim[1];
    prim[1] = 0;
   };
  };
 };
 
 return 0;
 
};
 
Zuletzt bearbeitet:
hallo, hier noch meine lösung,...
vielleicht mach ich dann später noch die ausgabe in eine datei,...
aber erstmal so:

Code: 
#include <stdio.h>
#include <math.h>

unsigned long int find_next_prime(unsigned long int);

int main( void )
{
    unsigned long int von, first, second;
    unsigned int anz, zaehler;

    printf("\n\nVon welcher Zahl an sollen Primzahlenpaare gesucht werden?\n");
    scanf("%lu", &von);
    printf("Wie viel Primzahlenpaare sollen gefunden werden?\n");
    scanf("%u", &anz);

    zaehler = 0;

    while(zaehler < anz)
    {
        first = find_next_prime(von);
        second = find_next_prime(first);
        if(second - first == 2)
        {
            zaehler++;
            printf("\n%9u: %11lu    || %11lu", zaehler, first, second);
        }
        von = first;
    }

    getchar();
    printf("\n\n\n  DANKE und TSCHÜSS !!!\n\n  Press Enter to Exit ;)  ....  ");
    getchar();

    return 0;
}

unsigned long int find_next_prime(unsigned long int x)
{
        bool its_a_prime = true;
        if( x % 2 == 0 ) x++;
        if( x < 3 ) return 3;
        else
        {
                do
                {
                        its_a_prime = true;
                        x+=2;
                        for(unsigned long int i = 2; i < sqrt(x) + 1; i++)
                        {
                                if( (x % i) == 0 )
                                {
                                        its_a_prime = false;
                                }
                        }
                }while( !its_a_prime );
        }
        return x;
}
unter linux mit g++.

lg lukas
 
da ich gerade am python lernen bin hier auch noch meine Lösung...

Code: 
import math
def primepair(start,end):
	primes = [2]
	for i in range(3,end+1,2):
		for x in primes:
			if x>math.sqrt(i):
				continue
			if i%x==0:
				break
		else:
			if((i-primes[-1]==2)&(primes[-1]>=start)):
				print("%d - %d" % (primes[-1], i))
			primes.append(i)

//edit: kleine Änderung weil mir jetzt eingefallen ist warum ich mein if-statement nicht mit & verbinden konnte...
 
Zuletzt bearbeitet:
Hi,

ich habe das ganze mal in Python gemacht, da ich momentan Python lerne und
diese Übung als passend empfand :)

Code: 
#!/usr/bin/python

startwert = 3
endwert = input("Endwert: ")
zahl = 5
test = 0

print startwert, " - ", zahl

while  zahl < endwert:
  test = zahl % 3
  test2 = startwert % 3
  if test != 0 and test2 != 0:
    print startwert, " - ", zahl
  startwert = startwert + 2
  zahl = zahl + 2
 
Zuletzt bearbeitet:
foxtrot92 hat gesagt.:
Hi,

ich habe das ganze mal in Python gemacht, da ich momentan Python lerne und
diese Übung als passend empfand :)
Zum Vergrößern anklicken....
in der Ausgabe sollten nur Primzahlenpaare sein ;)
Code: 
3  -  5
5  -  7
7  -  9 <--
-->9  -  11
11  -  13
13  -  15<--
-->15  -  17
17  -  19
19  -  21<---
http://de.wikipedia.org/wiki/Primzahl hat gesagt.:
Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler
Zum Vergrößern anklicken....
 
foxtrot92 hat gesagt.:
Hi,

Ich habe den kleinen aber wichtigen fehler bei meinen Skript ausgemerzt.
Danke CDW für deine Aufmerksamkeit:wink:
Zum Vergrößern anklicken....
*hust*
Code: 
5  -  7
11  -  13
17  -  19
23  -  25<--- (5*5)
29  -  31
(5*7)--->35  -  37
41  -  43
47  -  49 <--- 7 * 7
53  -  55<--- 5*11
Eine Primzahl ist nur durch sich selbst und durch 1 teilber.
Also eine Modulo 3 Operation ist leider kein ausreichender Primzahlentest - sonst hätte man sich aufwändige Verfahren (Miller Rabin, Solovay, Lucas) für große Zahlen auch sparen können ;).
 
Auch wieder was von mir, hab hier aber keinen Server zum testen:
PHP: 
function istPrim($teste) {
				$i = 2;
				while($i < $teste && $teste%$i != 0)
					$i++;
				if($i == $teste)
					return TRUE;
				else
					return FALSE;
			}

			function primZahlPaare($limit) {
				$ergebnis = "<table>";

				for($i = 3; $i+2 <= $limit; $i+=2) {
					if(istPrim($i) && istPrim($i+2))
						$ergebnis = $ergebnis.'<tr><td>'.$i.'</td><td>'.($i+2).'</td></tr>';
				}
				return $ergebnis;
			}
			echo primZahlPaare(50);

Aufgerufen wird die Funktion primZahlPaare (mit dem entsprechenden Parameter).
LG, Micha
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben