Hackerboard Wiki HaboBlog
Hackerboard bei Facebook Hackerboard bei Google+ Hackerboard bei Twitter

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

Aufgabe Nr. 1: Primzahlenpaare

Diskussion: Aufgabe Nr. 1: Primzahlenpaare im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige Hey nachdem ich hier die Lösungen angeschaut habe, gehen die meisten hier nach folgendem Schema vor: Man bekommt n, ...

Like Tree2Likes

Antwort
Alt 08.06.11, 13:02   #31 (permalink)
 
Benutzerbild von Scutus
 
Registriert seit: 02.09.10
Scutus Leistung: Pentium IScutus Leistung: Pentium IScutus Leistung: Pentium I
Scutus eine Nachricht über ICQ schicken Scutus eine Nachricht über Skype™ schicken
Likes: 21
Standard

Anzeige

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:

Java   
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
Scutus ist offline   Mit Zitat antworten
Alt 06.07.11, 11:57   #32 (permalink)
 
Registriert seit: 05.07.11
Python-Fx Leistung: Facit NTK
Likes: 0
Standard 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;
 
};

Geändert von Python-Fx (07.07.11 um 06:42 Uhr)
Python-Fx ist offline   Mit Zitat antworten
Alt 09.07.11, 14:51   #33 (permalink)
 
Registriert seit: 08.07.11
_Sakul_ Leistung: Facit NTK
Likes: 0
Standard

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
_Sakul_ ist offline   Mit Zitat antworten
Alt 10.04.12, 19:35   #34 (permalink)
 
Registriert seit: 04.09.10
Ae0n Leistung: Facit NTK
Likes: 0
Lightbulb

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...

Geändert von Ae0n (11.04.12 um 00:17 Uhr)
Ae0n ist offline   Mit Zitat antworten
Alt 13.04.12, 15:00   #35 (permalink)
 
Registriert seit: 12.04.12
foxtrot92 Leistung: Facit NTK
Likes: 0
Standard

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

Geändert von foxtrot92 (23.04.12 um 16:33 Uhr) Grund: Verbesserung des Codes, dank CDWs aufmerksamkeit (Danke CDW)
foxtrot92 ist offline   Mit Zitat antworten
Alt 13.04.12, 15:56   #36 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

Zitat:
Zitat von foxtrot92 Beitrag anzeigen
Hi,

ich habe das ganze mal in Python gemacht, da ich momentan Python lerne und
diese Übung als passend empfand
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<---
Zitat:
Zitat von http://de.wikipedia.org/wiki/Primzahl
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
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 23.04.12, 16:35   #37 (permalink)
 
Registriert seit: 12.04.12
foxtrot92 Leistung: Facit NTK
Likes: 0
erledigt

Hi,

Ich habe den kleinen aber wichtigen fehler bei meinen Skript ausgemerzt.
Danke CDW für deine Aufmerksamkeit
__________________
Python ist ein Schlange
foxtrot92 ist offline   Mit Zitat antworten
Alt 23.04.12, 20:01   #38 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

Zitat:
Zitat von foxtrot92 Beitrag anzeigen
Hi,

Ich habe den kleinen aber wichtigen fehler bei meinen Skript ausgemerzt.
Danke CDW für deine Aufmerksamkeit
*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 .
Tarantoga and benediktibk like this.
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 22.05.12, 14:21   #39 (permalink)
 
Registriert seit: 22.05.12
MichaBe Leistung: Facit NTK
Likes: 0
Standard

Auch wieder was von mir, hab hier aber keinen Server zum testen:
   
PHP-Code:
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+<= $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

Geändert von MichaBe (23.05.12 um 11:12 Uhr) Grund: Hab noch ein paar Fehler gefunden und behoben...
MichaBe ist offline   Mit Zitat antworten
Antwort
   
- Anzeige -

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » Aufgabe Nr. 1: Primzahlenpaare
Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus


Ä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


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61