002
06.01.2007, 16:19 Uhr
~Starsurfer
Gast
|
so wieder ein bisschen modifiziert:
500000 Primzahlen -> ~2.6 sec
1000000 Primzahlen -> ~6.8 sec
10000000 Primzahlen -> ~238 sec
| C++: |
//---------------------------------------------------------------------------
#include <iostream>
#include <windows>
#include <cmath>
using namespace std;
//---------------------------------------------------------------------------
int main()
{
unsigned int ges_anzahl,akt_zahl,stempel_loop;
unsigned int *prim_liste, //dyn array für primzahlen
*akt_prim_adresse, //zeiger auf element von prim array
*akt_zahl_adresse, //zeiger auf akt_zahl
*array_start_adresse,
*array_end_adresse,
*array_akt_adresse,
*akt_stempel_adresse;
bool ist_prim;
LONGLONG frequenz, end_zeit, start_zeit;
double TimeScale;
unsigned int stempel[8]={1,7,11,13,17,19,23,29}; //Netz des Ulam
cin >> ges_anzahl;
// dyn array mittels new erzeugen ist nicht schneller
if((prim_liste=(unsigned int *) malloc(sizeof(unsigned int)*ges_anzahl))==NULL)//dyn array erzeugen
{
cout << "Nicht genug Speicher fuer Array\n\n";
system("Pause");
return 0;
}
prim_liste[0]=2; //erste 3 primzahlen setzen
prim_liste[1]=3; //
prim_liste[2]=5; //
akt_zahl=3; //start parameter setzen
stempel_loop=0; //
akt_stempel_adresse=&stempel[1]; //pointer addressen übergeben
akt_zahl_adresse=&akt_zahl; //
array_start_adresse=&prim_liste[0]; //
array_akt_adresse=&prim_liste[3]; //
array_end_adresse=&prim_liste[ges_anzahl]; //
QueryPerformanceFrequency((LARGE_INTEGER*) &frequenz); //system freq ermitteln
QueryPerformanceCounter((LARGE_INTEGER*) &start_zeit); //anfangszeit ermitteln
TimeScale = 1.0/frequenz;
//filtern
do
{
akt_prim_adresse=prim_liste;
ist_prim=true;
for(int i=1;i<array_akt_adresse-array_start_adresse;i++)
{
akt_prim_adresse++;
if((*akt_zahl_adresse)%(*akt_prim_adresse)==0)
{
ist_prim=false;
break;
}
if((*akt_prim_adresse)*(*akt_prim_adresse)>(*akt_zahl_adresse))break;
}
if(ist_prim==true)
{
*array_akt_adresse=(*akt_zahl_adresse);
array_akt_adresse++;
}
(*akt_zahl_adresse)=(*akt_stempel_adresse)+30*stempel_loop; //
akt_stempel_adresse++; //
if(akt_stempel_adresse>&stempel[7]) // Netz des Ulam
{ //
akt_stempel_adresse=stempel; //
stempel_loop++; //
}
}while(array_akt_adresse<array_end_adresse);
//filtern
QueryPerformanceCounter( (LARGE_INTEGER*) &end_zeit); //endzeit ermitteln
cout << "\n";
//for(unsigned int i=0;i<ges_anzahl;i++){cout << prim_liste[i] << "\n";}//ausgeben
cout << "\nGefilterte Primzahlen: " << ges_anzahl << "\n";
cout << "Zeit: " << (end_zeit - start_zeit) * TimeScale << " s\n\n";
free(prim_liste);
system("Pause");
return 0;
}
//---------------------------------------------------------------------------
|
mmmh mir hat zwar noch keiner geantwortet  aber vll hab ich ja Glück:
Gibts ne alternative zu modulo? ich brauch ja nich den genauen Rest wissen, ich brauch ja nur wissen obs teilbar is oder net...
Starsurfer |
