006
23.06.2004, 17:58 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Der algo ist falsch: geringfügig beser wäre:
| C++: |
#include <iostream>
int main()
{
for(int kandidat=1;kandidat<101;kandidat=kandidat+1)
{
bool istPrimzahl = true;
for(int teiler=2;istPrimzahl && teiler<kandidat; teiler++)
{
istPrimzahl = kandidat%teiler!=0;
}
if (istPrimzahl)
{
std::cout<<kandidat<<std::endl;
}
}
}
|
Du kannst das aber noch sehr weitgehend optimieren:
Zunächst ist klar, daß 2 die einzige durch zwei teilbar Primzahl ist, sie ist sogar die erste. Alle anderen Primzahlen sind ungrade. Deshalb kann man kandidat dann immer um zwei hochzählen:
| C++: |
...
std::cout<<2<<std::endl;
for(int kandidat=3;kandidat<101;kandidat+=2)
{
bool istPrimzahl = true;
for(int teiler=2;istPrimzahl && teiler<kandidat; teiler++)
{
istPrimzahl = kandidat%teiler!=0;
}
if (istPrimzahl)
{
std::cout<<kandidat<<std::endl;
}
}
...
|
Weiterhin kann man sagen, daß als Teiler nur die zahlen in Frage kommen, die kleiner oder gleich der Wurzel von kandidat sind:
| C++: |
...
std::cout<<2<<std::endl;
for(int kandidat=3;kandidat<101;kandidat+=2)
{
bool istPrimzahl = true;
for(int teiler=3;istPrimzahl && teiler*teiler<=kandidat; teiler+=2)
{
istPrimzahl = kandidat%teiler!=0;
}
if (istPrimzahl)
{
std::cout<<kandidat<<std::endl;
}
}
...
|
Speziell für Deine Aufgabe möglichweise schon eine akzeptable Lösung; für größere zahlenbereiche solltest Du dann vielleicht mit dem sieb arbeiten.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
