# Primzahlen herausbekommen!



## mich_blume (14. April 2004)

Hi an alle,

ich bin neu bei der c++-Programmierung und habe auch gleich eine Aufgabe bekommen, die (zumindest für mich) nich ganz so einfach ist. So soll ich zum  Beispiel die x. Primzahl ausgeben. Das x wird vom Benutzer eingeben und daraufhin die Berechnung ausgeführt.
Bisher habe ich an arrays gedacht zum speichern der Werte, aber da man ja die größe des arrays fest bestimmen muss, wiess ich nicht so recht wie das am besten zu gestalten wäre.

Besten Dank schon mal im vorraus

Michael


----------



## Steiner_B (14. April 2004)

Mit diesem Programm müsste es gehen. Es könnte nur sein das du einige Kleinigkeiten ändern musst. (Funktioiert sicher unter Dev-Cpp 4.9.8.5)


```
#include <iostream.h>
#include <conio.c>

void main()
{
int Zahl=1;
int Counter=0;
int Input, Last_Priem;
bool priem=true;

cout<<"Geben Sie an die wievielte Priemzahl sie wollen : ";
cin>>Input;

while(Counter<Input)
   {
   priem=true;
   for (int j=2;j<Zahl;j++)
      {
      if (Zahl%j==0)
            {
            priem=false;
            j=Zahl;
            }
      else if (Zahl%j!=0)
            {
            priem=true;
            Last_Priem=Zahl;
            }
      }
   if (priem==true)
      {
      Counter++;
      }
   Zahl++;
   }
   
   cout<<"Die "<<Input<<". Priemzahl ist "<<Last_Priem;
   getch();
}
```


----------



## Matthias Reitinger (14. April 2004)

Sollte ein bisschen schneller sein:


```
#include <iostream>
using namespace std;

int main()
{
	int iGesucht, iAktuell = 0, iKandidat = 1, iKandidatHalbe, iTeiler;
	bool bIstPrim;

	cout << "Zu ermittelnde Primzahl Nr.: ";
	cin >> iGesucht;

	while (iAktuell < iGesucht) {
		bIstPrim = true;
		++iKandidat;
		iKandidatHalbe = iKandidat >> 1;
		for (iTeiler = 2; iTeiler < iKandidatHalbe; ++iTeiler) {
			if (iKandidat % iTeiler == 0) {
				bIstPrim = false;
				break;
			}
		}
		if (bIstPrim) {
			++iAktuell;
		}
	}

	cout << "Die " << iGesucht << ". Primzahl lautet: " << iKandidat;
	
	return 0;
}
```


----------



## RedWing (16. April 2004)

> ```
> for (iTeiler = 2; iTeiler < iKandidatHalbe; ++iTeiler) {
> if (iKandidat % iTeiler == 0) {
> bIstPrim = false;
> ...




```
for (iTeiler = 2; iTeiler * iTeiler < iKandidat; ++iTeiler) {
			if (iKandidat % iTeiler == 0 ) {
				bIstPrim = false;
				break;
			}
```

Sollte bei großen Zahlen noch schneller gehen, da man nur bis zur Wurzel der eingegebenen Zahl überprüfen brauch.

Gruß RedWing


----------



## Matthias Reitinger (17. April 2004)

Darüber ließe sich jetzt streiten - schleißlich muss da auch bei jedem Schleifendurchlauf das Produkt iTeiler * iTeiler berechnet werden.


----------



## RedWing (17. April 2004)

Nein das denk ich nicht das es ein Streithema ist,
weil dann dein Shifting wegfällt und dafür das mal hinzukommt also nix eingebusst,
ausserdem denk ich ist es besser bei grossen Zahlen nur bis zur Wurzel zu gehen als jedesmal bis zur Hälfte.Und da das ganze quadratische Komplexität hat
ist meine Version schon eine leichte Verbesserung...
Ein Beispiel:
625:
Bei dir musst  du alle Teiler bis 312 überprüfen
bei meinem Beispiel brauch ich dies nur bis 25 zu tun....

Solte nur eine konstruktive Kritik sein 


MfG

RedWing


----------



## Matthias Reitinger (17. April 2004)

Ich hab's grad mal ausprobiert, deine Methode ist tatsächlich um einiges schneller 

Ich muss dir allerdings widersprechen, wenn du sagst dass die Berechnung des Produkts ohne Performanzverlust das Shifting ersetzt, denn:
1. wird ein Shifting prozessorintern schneller abgearbeitet (hab das was mit Faktor 3 im Kopf, weiß aber nicht wie aktuell das noch ist)
2. wird bei meiner Methode das Shifting _einmal pro Primzahlkandidat_ durchgeführt, bei dir die Multiplikation jedoch _einmal pro Teileruntersuchung jedes Primzahlkandidaten_.

Es ist also nur die Tatsache, dass es quadratisch weniger Schleifendurchläufe sind, die dafür verantwortlich ist, dass der Geschwindigkeitsverlust ausgeglichen und sogar in's negative verlagert werden kann.

Ich wusste nur nicht, welche von beiden Einwirkungen überwiegt, deswegen meine Zweifel


----------



## Steiner_B (18. April 2004)

Aber funktioniert haben alle, und das ist doch das wichtigste daran!


----------



## revelation (18. April 2004)

Hallo zusammen!

Ich mische mich ja ungern ein, aber der Algo von Steiner_B ist fehlerhaft!
1. Versucht mal die erste bzw zweite Primzahl zu ermitteln! - Ergebnis: Müll!
Diese Schleife 





> for (int j=2;j<Zahl;j++)


 wird dann nämlich nie durchlaufen, das bedeutet Last_Prim enthält am Ende noch immer den willkürlichen Memorywert, der sich an der Adresse von Last_Prim befindet!
2. Wird nicht die gesuchte, sondern die eine Primzahl vorher zurückgeben: bsp: gibt man 4 an liefert das Programm 5 statt 7 (2,3,5,7,11,13...)! Bei 5 liefert es 7 statt 11!

(Wollte hier niemanden beleidigen, sondern nur etwas richtigstellen!)

Gruß
Johannes


----------



## Matthias Reitinger (18. April 2004)

Dann ist mein Quellcode allerdings auch fehlerbehaftet.

Bugfix:
Die entsprechende Zeile ersetzen:

```
for (iTeiler = 2; iTeiler <= iKandidatHalbe; ++iTeiler) {
```


----------



## revelation (18. April 2004)

Wollte mal ausprobieren ob es noch schneller geht - und JA, es geht! 

Hier der Code:
	
	
	



```
__inline int JSqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5f;
    
    x2 = number * 0.5f;
    y  = number;
    i  = * (long *) &y;      // evil floating point bit level hacking
    i  = 0x5f3759df - (i >> 1);             // what the fuck?
    y  = * (float *) &i;
    y  = y * (threehalfs - (x2 * y * y));   // 1st iteration
    //y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
    
    return (int) (1/y);
}

__inline bool is_prim(int zahl)
{
    bool isprim = true;
    int sqr_zahl = JSqrt((float) zahl);
    
    for(int i = 2; i <= sqr_zahl; ++i)
        if(zahl % i == 0)
        {
            isprim = false;
            break;
        }
    return isprim;        
}

int get_prim_number(int num)
{    
    int akt_num = 1, prim_count = 2;
    
    if(num == 1)
       return 2;

    while(prim_count <= num)
    {
        akt_num += 2;
        
        if(is_prim(akt_num))
            ++prim_count;                   
    }
    
    return akt_num;
}
```
Die JSqrt-Funktion habe ich mir von dem netten Herrn Carmack geborgt (aus der Quake-Engine. Leider entzieht sich ihre Funktionsweise meiner Kenntniss ). Der Code ist aber auch mit der normalen sqrt-funktion schneller!

Gruß
Johannes

PS: Ich weiß, dass sich mein Code eigentlich nur an zwei Stellen wesentlich unterscheidet:





> for (iTeiler = 2; iTeiler * iTeiler < iKandidat; ++iTeiler)


->
	
	
	



```
int sqr_zahl = JSqrt((float) zahl);
    
for(int i = 2; i <= sqr_zahl; ++i)
```

es muss nur einmal dir Wurzel gezogen werden, anstatt immer das Produkt des Zählvariablen zu berechnen.

Und 





> ++iKandidat;


-> 
	
	
	



```
akt_num += 2;
```
Da es außer der 2 sowiso keine geraden Primzahlen gibt, reicht es die ungeraden zu prüfen - die hälfte der Schleifendurchläufe wird eingespart.


----------

