[HaBo]

Indi · 23.05.03, 12:59

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.

PeaceTreaty · 23.05.03, 15:05

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;

}

HaBo Ads

Indi · 23.05.03, 16:00

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.

Nornagest · 23.05.03, 16:40

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;
}

Nornagest · 23.05.03, 20:09

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

blue · 21.06.03, 13:54

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]

Blackvirus · 22.03.04, 17:29

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

2wros · 09.05.04, 15:18

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

Ray · 09.05.04, 18:15

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

zovax · 09.05.04, 20:31

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();

		}
	}

Zitat:

Wi gebt ihr denn den Quelltext so in Extraform an?

Unter Antwort erstellen deinen Code zwischen zwei [ CODE] [/CODE] Tags stellen.

Zirias · 09.05.04, 22:00

Zitat:

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.

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

ivegotmail · 09.05.04, 23:49

wer eine wirklich gute optimierung zur primzahlenberechnung sucht, sollte sich mal das sieb des Eratosthenes anschauen
bzw den Miller-Rabin-Test für sehr hohe primzahlen

http://www.jjam.de/Java/Applets/Prim...tosthenes.html
http://www.jjam.de/Java/Applets/Prim...ler_Rabin.html

Zirias · 10.05.04, 00:42

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

Eydeet · 17.03.07, 12:39

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;
}

phonix28888 · 27.03.07, 19:19

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;
		
}

Empfehlung

23.05.03, 12:59	#1 (permalink)
Indi Member of Honour Registriert seit: 02.10.01 Likes: 0	Aufgabe Nr. 1: Primzahlenpaare 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.

09.05.04, 15:18	#8 (permalink)
2wros Registriert seit: 09.05.04 Likes: 0	RE: Aufgabe Nr. 1: Primzahlenpaare 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

09.05.04, 23:49	#12 (permalink)
ivegotmail Member of Honour Registriert seit: 28.05.03 Likes: 1	wer eine wirklich gute optimierung zur primzahlenberechnung sucht, sollte sich mal das sieb des Eratosthenes anschauen bzw den Miller-Rabin-Test für sehr hohe primzahlen http://www.jjam.de/Java/Applets/Prim...tosthenes.html http://www.jjam.de/Java/Applets/Prim...ler_Rabin.html __________________ http://livehabo.hackerboard.de \| http://livebb.sourceforge.net

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

09.05.04, 18:15	#9 (permalink)
Ray Registriert seit: 06.08.02 Likes: 0	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

10.05.04, 00:42	#13 (permalink)
Zirias Registriert seit: 16.04.04 Likes: 0	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


HaBo Ads HaBOT

[HaBo]

Aufgabe Nr. 1: Primzahlenpaare