Aufgabe Nr. 1: Primzahlenpaare

I

Indi

Member of Honour
Aufgabe ist es alle Primzahlenpaare innerhalb eines bestimmten Bereichs aufzulisten, wobei der Anfangswert bzw. der Endwert vom Benutzer festgelegt werden können sollte (dh. keine fixen Werte), und jeweils ein Primzahlenpaar in einer Zeile dargestellt werden sollte. Eine tabellarische Aufzählung wäre von Vorteil (in C zb. mit Tabulator \t oder bei einem PHP-Script mit einer generierten Tabelle).

Anmerkung:
Primzahlenzwillinge sind Paare von Primzahlen deren Differenz 2 beträgt; zb. 3 und 5 oder 5 und 7

Beispiel:
Bei einer Eingabe eines Startwertes von 1 und einem Endwert von 30 erfolgt folgende Ausgabe:

3 - 5
5 - 7
11 - 13
17 - 19

Wobei 1 und 3 kein Primzahlenpaar ist, da 1 nicht als Primzahl angesehen wird.

Eine Lösung in C wird in den folgenden Tagen online sein. Wenn ihr selbst eine Lösung zu dieser Aufgabe habt, stellt sie online und postet einen Link oder kopiert direkt den Code rein.
 
Bin mir nicht sicher obs so passt:

Code: 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isprimzahl(int value)
{
	int tempo = 0;
	int testa = 0;

	if (value == 0)
		return -1;
	
	for(tempo = 2; tempo < value; tempo++)
	{
		testa = value % tempo;

		if ( (testa == 0) && (tempo != value) && (tempo != 1))
				return 0;
	}

	return 1;
}

int main(int argc, char *argv[])
{
   int min_val = 0;
   int max_val = 0;
   int i = 0;	
   int err = 0;
   int diff = 0;
   int primlast = 0;
   
   if (argc != 3)
   {
   	fprintf(stderr,\"Usage: %s <min> <max>\n\", argv[0]);
	return 0;
   }

   if( (strlen(argv[1]) > 5) || (strlen(argv[2]) > 5) )
   {
   	fprintf(stderr,\"Usage Error...\n\");
	return 0;
   }

   min_val = atoi(argv[1]);
   max_val = atoi(argv[2]);

   if (min_val >= max_val)
   {
	   fprintf(stderr,\"<max> must be bigger than <min>\n\");
	   return 0;
   }

   for(i = min_val; i <= max_val; i++)
   {
	   err = isprimzahl(i);

	   if(err == 1)
	   {
		   if(primlast == 0)
		   {
			   primlast = i;
			   continue;
		   }

		   if(primlast > 0)
		   {
			   if( (i - primlast) == 2)
				   printf(\"%d\t%d\n\",primlast,i);

			   primlast = i;
		   }
	   }
   }

   return 0;

}
 
Und das is mein Code hier:

Code: 
#include <stdio.h>
int primzahl(int zahl);

main()
{
	int x, y;
	printf(\"Start: \");
	scanf(\"%i\",&x);
	printf(\"\nEnde: \");
	scanf(\"%i\",&y);

	if (x % 2 == 0) // Auf ungerade Zahl stellen
		x++;

	for (x;x<=y;x++)
	{
		if (primzahl(x) == 1 && primzahl(x+2) == 1) // Check auf PrimPaar
			printf(\"%i\t\t%i\n\",x,x+2);
		x++;
	}	
	printf(\"\n\");
	return 0;
}

primzahl(zahl)
{
	int i;
	if (zahl <= 1)
		return 0;
	for (i=2;i<=zahl/2;i++)
	{
		if (zahl % i == 0)
			return 0; // Primzahl: Nein
	}
	return 1; // Primzahl: Ja
}

Anmerkung:
Die Primzahlen-Paare innerhalb des Bereiches 1 bis 50 sind wie folgt:
3 - 5, 5 - 7, 11 - 13, 17 - 19, 29 - 31, 41 - 43;
Die stimmen mit denen von PeaceTreaty überein und sollten nach kurzem Kopfrechnen wirklich richtig sein.
 
weil peace es wollte mein Beitrag:

Code: 
#include <iostream>
#include <cmath>

bool isPrim(long zahl)
{
	if(zahl<2)
		return false;
	for(long i=2 ; i <= static_cast<long>(sqrt(static_cast<double>(zahl))) ; ++i)
		if( zahl%i == 0)
			return false;
	return true;
}

int main()
{
	long min, max;
	min=max=0;
	std::cout<<\"Bitte untere Grenze eingeben: \";
	std::cin>>min;
	std::cout<<\"Bitte obere Grenze eingeben: \";
	std::cin>>max;
	min= (min%2==0 ? (min+1) : min);
	for(long i=min;i<=max;++i)
		if(isPrim(i) && isPrim(i+2))
			std::cout<<i<<\"\t\"<<i+2<<\"\n\";
	return 0;
}
 
und weil ichs nich lassen kann:
wer die ausgabe lieber in ner datei will macht folgendes

Code: 
#include <fstream>

und

Code: 
for(long i=min;i<=max;++i)
if(isPrim(i) && isPrim(i+2))
std::cout<<i<<\"\t\"<<i+2<<\"\n\";

ändert man zu:

Code: 
std::ofstream ausgabe;
ausgabe.open(\"ausgabe.txt\",std::ios_base::out);
for(long i=min;i<=max;++i)
if(isPrim(i) && isPrim(i+2))
ausgabe<<i<<\"\t\"<<i+2<<\"\n\";
ausgabe.close();

mfg
Nornagest
 
und hier hab ich es mal in object-pascal geschrieben:
Code: 
var
     min,max,t,z,v:Integer;
     a,b: string;
begin
  a := '';
  b := '';
  Listbox1.Items.Clear;
  min := strtoint(edit1.Text);
  max := strtoint(edit2.Text)+1;
  for z := min to max do
  begin
    t := 2;
    while (z mod t <> 0) AND (t < z) do t := t+1;
    if z = t then
    begin
      if a = '' then a := inttostr(z) else
      if b = '' then b := inttostr(z) else
      begin
        v := strtoint(b);
        if strtoint(a)+2 = strtoint(b) then listbox1.Items.Add(a+' - '+b);
        a := inttostr(z);
        if v+2 = strtoint(a) then  listbox1.Items.Add(inttostr(v)+' - '+a);
        b := '';
      end;
    end;
  end;
end;
[Edit] Shit hab bei der Aufgabenstellung was überlesen... werds ausbessern :-D[/EDIT]
...
[EDIT]Habs ausgebessert.[/EDIT]
 
Hi!

Kommt zwar ein bisschen spät, aber ich bin noch nicht "solange" dabei.
Ich habs in C geschrieben, ist nicht wirklich lang

Code: 
//1. Aufgabe - Primzahlenpaare
//by Blackvirus

//Dieses Programm gibt die Primzahlenpaare in einem bestimmten Bereich aus
//Primzahlenpaar sind zwei Primzahlen die sich nur um 2 unterscheiden

#include <stdio.h>
#include <conio.h>


main()
	{
	int start,ende,prim, i,k,j=0,primzahlen[1000];
	printf("\t\tP R I M Z A H L E N - P A A R   A U S G A B E");
	printf("\n\nBitte geben Sie die Startzahl ein: ");
	scanf("%d",&start);
	printf("\nBitte geben Sie die Endzahl ein: ");
	scanf("%d",&ende);
	printf("\n\nPAARE:\n\n");

	if(start<=3 && ende>=3)		primzahlen[j]=3;	j++;	//Wenn der Start kleiner als 3 ist
															//und das Ende größer ist, wird 3 "dazugehängt"
	for(i=start;i<=ende;i++)
		{
		prim=1;
		k=2;
		while(prim==1 && k<=(i/2))				//Zahl soll solange überprüft werden						
			{									
			if(i%k==0)	prim=0;					//bis sie durch eine Zahl nicht "glatt" teilbar ist
			k++;
			}
		if(prim==1)								//Wenn die Zahl eine Primzahl ist										
			{									//soll sie zum String mit den Primzahlen 
			primzahlen[j]=i;					//"dazugehängt" werden
			j++;
			}
		}
	j=0;	

	//Wenn sich zwei Primzahlen nur um 2 unterscheiden, soll das Paar ausgegeben werden

	while(primzahlen[j]!='\0')
		{					
		if(primzahlen[j]+2==primzahlen[j+1])	printf("%d - %d\n",primzahlen[j],primzahlen[j+1]);
		j++;
		}
	getch();
	}

MfG

Blackvirus
 
Servus, ich hab hier mal meine lösung anzubieten, geschrieben in Java. Wi gebt ihr denn den Quelltext so in Extraform an?
Code: 
import java.lang.*;
import java.lang.Integer;



public class Primzahlen {

static int k,l,m,n,o;


public static void main(String args[])
    {
	
	l = Integer.parseInt(args[1]);
		
       for( k = Integer.parseInt(args[0]) ; k <= l ; k++ )
        {
            if (k == 1)
            k = k + 2 ;

            for( m = 2; m < k ; m++ )
            {
            n = 0;

                if(k % m == 0)
                {
                n++;
                break;
                }

            }
            if (n==0)
              {
              if (k - o == 2)
              System.out.println(o + " - " + k);
              o = k;

              }
          }
    
        }
     }
probieren Sie's dann wissen Sie's. übrigens versuche ich EurenCode mal mit dem Cbuilder nachzuvollziehen aber der gibt mir bei jedem irgendnen Fehler aus wenn ich Euren Quellcode mit copy und paste testen will. Thomas
 
Mal so als Tip am Rande:

Wenn bei der Überprüfung, ob x prim ist, nur bis Wurzel(x) gesucht wird, geht das ganze wesentlich schneller vonstatten. Noch schneller geht's, wenn bei jedem Schritt der Betrag des angenommenen Teilers um 2 erhöht wird anstatt um 1.

@Norna: Ja, ich hab's gesehen. :-P
 
Der Volllständigkeit halber, nun das ganze nochmal in C#:

Code: 
using System;

namespace Primzahlen
{
	public class CPrim
	{
		internal bool istPrim(int iMin)
		{
			int min = iMin;

			if(min < 2)
				return false;
			for(int i = 2; i <= iMin/2; i++)
			{
				if(min % i == 0)
					return false;
			}
			return true;
				
		}
	}
}




	 class CHauptklasse
	{
		 static int iMin;
		 static int iMax;

		static void Main()
		{

			Primzahlen.CPrim obj = new Primzahlen.CPrim();

			for (int i = 0; i != 3; i = i)
			{
				Console.Write("Bitte geben sie die untere Grenze ein: ");
				iMin = Convert.ToInt32(Console.ReadLine());

				Console.Write("Bitte geben sie die obere Grenze ein: ");
				iMax = Convert.ToInt32(Console.ReadLine());

				if(iMin > iMax)
				{
					Console.WriteLine("{0} ist größer als {1}", iMin, iMax);
					i = 2;
				}
				else
					i = 3; 
			}

			if(iMin % 2 == 0)
				iMin++;

			for(iMin = iMin; iMin <= iMax; iMin = iMin +2)
			{
				if(obj.istPrim(iMin) && obj.istPrim(iMin+2))
					Console.WriteLine("Primpaar: {0} und {1}", iMin, iMin+2);
			}

			Console.ReadLine();

		}
	}
Wi gebt ihr denn den Quelltext so in Extraform an?
Zum Vergrößern anklicken....
Unter Antwort erstellen deinen Code zwischen zwei [ CODE] [/CODE] Tags stellen.
 
Original von Damien
Wenn bei der Überprüfung, ob x prim ist, nur bis Wurzel(x) gesucht wird, geht das ganze wesentlich schneller vonstatten. Noch schneller geht's, wenn bei jedem Schritt der Betrag des angenommenen Teilers um 2 erhöht wird anstatt um 1.
Zum Vergrößern anklicken....

Mir kam da vor ein paar Tagen noch eine ungewöhnlichere Optimierung in den Sinn. Was, wenn man auch die 3er-Zahlen nicht betrachten müsste? Übrig blieben die Zahlen 5, 7, 11, 13, 17, 19, ... Man sieht schnell, dass die Differenz zweier Folgeglieder zwischen +4 und +2 alterniert. Das ist aber schön, denkt man sich da, denn 2 = (4 XOR 6) und 4 = (2 XOR 6). Man kann also mit derselben Operation aus einer 4 eine 2 und umgekehrt machen. Noch schöner: XOR ist eine Elementaroperation, die direkt auf Registerebene ausführbar ist, die Kosten sind also sehr gering. Die Einsparung (jeder 6. Schleifendurchlauf) dagegen recht hoch :)

Hier mal eine Beispielfunktion in C, die mit dieser Optimierung Primzahlen berechnet. Ich war leider zu faul zum kommentieren, ich hoffe ihr versteht sie trotzdem *g* (Ach ja, sie ist natürlich auf 32bit-Architekturen optimiert, für 64bitter kann man als Datentyp stattdessen uint64_t nehmen)

Code: 
uint32_t *prim(uint32_t max) {
        uint32_t n=1;
        uint32_t p,i;
        uint32_t *buf;
        double pred_n;
        char offset=4;
        
        pred_n=1.425*(max/log((double)max))+1;
        buf=(uint32_t*)malloc((long)pred_n*4);
        if (max>0) buf[n++]=1;
        if (max>1) buf[n++]=2;
        if (max>2) {
                buf[n++]=3;
                for (i=5; i<=max; i+=offset) {
                        offset^=6; /* hier wird der Offset zwischen 2 und 4 alterniert */
                        p=3;
                        do {
                                if ((i/buf[p])<buf[p]) {
                                        buf[n++]=i;
                                        break;
                                }
                        } while (i%buf[p++]);
                }
        }
        realloc(buf,n*4);
        *buf=n-1;
        return buf;
}

Zurückgegeben wird ein Zeiger auf ein Feld, im ersten Element steht die Anzahl der gefundenen Primzahlen. Wegen topic: Den code, um dann nur die Paare auszugeben (bzw überhaupt was auszugeben), spare ich mir jetzt (merker, vergleichen ob differenz = 2, wenn ja ausgeben), das ist IMO nebensächlich *g*

Greets, Ziri
 
Sorry, aber Sieb des Eratosthenes wird in den meisten Algorithmen in abgewandelter Form verwendet (so auch in meinem) und der andere Test ist leider nur bedingt brauchbar, man kann damit nur Primzahlen ausschließen, aber nie bestätigen (probabilistischer Algorithmus).

Greets, Ziri
 
Dieser Thread ist zwar schon etwas^^ älter, aber ich gehe mal davon aus, dass man die Programmieraufgaben jederzeit hochholen kann, da sie ja sozusagen nie gelöst sind, jedenfalls verstehe ich das so :)

Also hier meine recht schnelle Lösung, da mit dem Satz des Erastotenes:
Code: 
#include <iostream>

using namespace std;

int main()
{
    int max;

    cout << "   Primpaare   " << endl
            << "---------------" << endl;

    do {
        cout << "Max: ";
        cin  >> max;
    } while(max < 0 || max > 1000000);

    bool *isPrime = new bool[max];
    int lastPrime = -1;

    // Define every number (ex. 0+1) as true
    for(int i = 2; i < max; i++)
    {
        isPrime[i] = true;
    }

    for(int i = 2; i < max; i++)
    {
        if(isPrime[i])
        {
             // remove multiples
            for(int k = i * 2; k < max; k += i)
            {
                isPrime[k] = false;
            }

            if (lastPrime + 2 == i)
            {
                cout << lastPrime << ", " << i << endl;
            }

            lastPrime = i;
        }
    }

    delete[] isPrime;
}
 
Vorweg muss ich sagen das, das im grunde meine ersten Gehversuche bei sowas sind.
Ich glaube der Code ist nicht besonder effektiv, deshalb würde ich mich freuen wenn ihr mir Tipps geben könnte.
Leider gibts Probleme, wenn man die Grenze der zu testenden Zahlen zu hoch setzt. Warum konnte ich leider bist jetzt nicht rausfinden.
Das ganz ist in D geschrieben.


Code: 
import std.stdio;
	int anfang;
	int ende;
	int[1000] primzahlen;
	int anzahl=0;
	
	
	
void abfrage()
{	
	writef("Bereichanfang:");
	scanf("%d",&anfang);
	writef("Bereichende:");
	scanf("%d",&ende);
	abfragetest ();
}

void abfragetest ()
{
	if ( anfang >= ende)
	{
	writefln("Bereich unzulaessig. Neue Eingabe");
	abfrage();
	}
	if ( anfang < 3)
	{
	writefln("Bereichunzulaessig.Anfang muss > 2 sein. Neue Eingabe");
	abfrage();
	}
}

int primtest(int testobj)
{
	int ergebnis=0;
	for (int i = 0; primzahlen[i] != 0; i++)
	{
				
		if (testobj%primzahlen[i] == 0) 
		{
			ergebnis=0; 
			break;
		}
		else ergebnis = 1;
		
		
	}
	
if(ergebnis==1) return(testobj);
else return 0;
}


void paartest()
{
	
	for (int i = 0; i <= ende; i++)
	{
		if ( primzahlen[i]>=anfang)
		{
		int x=primzahlen[i+1]-primzahlen[i];
		
		if( x== 2) writefln( primzahlen[i]," und ",primzahlen[i+1]);
		}
	}
	
}





int main() {
	
	primzahlen[0] = 2; 
	abfrage ();
	writefln("Bereich:",anfang," bis ", ende);
	
	
	
	
	for (int i = 3; i <= ende; i++)
	{
		
	int neupri= primtest(i);
		if (neupri != 0) 
		{
		
		anzahl++;
		primzahlen[anzahl]=neupri;
		
				
		}
	}
	
	paartest();
		
return 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: 
<?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
	}
}
?>
 
naiver Algorithmus in D

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.
 
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)))
}
 
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!")
 
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
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben