Primzahlen Programm

Question

Ich versuche zur Zeit nur einige Fragen, um meine Programmierkenntnisse zu üben. (Nicht in der Schule oder irgendetwas noch nehmen, Autodidakt) Ich kam in diesem Problem, das mich verlangte in einer Reihe von einer gegebenen txt-Datei zu lesen. Diese Zahl wäre N. Jetzt bin ich nehme an, die n-te Primzahl für N <= 10 000. Nachdem ich es finden finden, ich bin nehme an, es auf eine andere txt-Datei auszudrucken. Jetzt für die meisten Teile der Frage, die ich bin in der Lage zu verstehen und ein Verfahren zu entwickeln zu bekommen N. Das Problem ist, dass ich ein Array bin mit zuvor gefundenen Primzahlen zu speichern, um sie zu verwenden, um gegen zukünftige Zahlen zu überprüfen. Auch wenn meine Array war Größe 100, solange der Eingang integer war etwa <15, stürzt das Programm ab.

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;

int main() {
    ifstream trial;
    trial.open("C:\\Users\\User\\Documents\\trial.txt");
    int prime;
    trial >> prime;
    ofstream write;
    write.open("C:\\Users\\User\\Documents\\answer.txt");
    int num[100], b, c, e;
    bool check;
    b = 0;
    switch (prime) {
        case 1:
        {
            write << 2 << endl;
            break;
        }
        case 2:
        {
            write << 3 << endl;
            break;
        }
        case 3:
        {
            write << 5 << endl;
            break;
        }
        case 4:
        {
            write << 7 << endl;
            break;
        }
        default:
        {
            for (int a = 10; a <= 1000000; a++) {
                check = false;
                if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
                {
                    for (int d = 0; d <= b; d++) {
                        c = num[d];
                        if ((a % c) == 0) {
                            check = true; // second filter based on previous recorded primes in array
                            break;
                        }

                    }
                    if (!check) {
                        e = a;
                        if (b <= 100) {
                            num[b] = a;
                        }

                        b = b + 1;
                    }
                }
                if ((b) == (prime - 4)) {
                    write << e << endl;
                    break;
                }
            }
        }
    }
    trial.close();
    write.close();
    return 0;
}

Ich habe diese ganz Basis auf meiner Attrappen Führung und selbst tut so etwas Code Ineffizienz und allgemeine newbie-ness meines Algorithmus vergeben. Auch für bis zu 15 es zeigt die Primzahlen korrekt.

Kann mir jemand sagen, wie ich über die Verbesserung dieser aktuellen Code gehen sollte? Ich denke, eine txt-Datei anstelle des Arrays zu verwenden. Ist das möglich? Jede Hilfe ist willkommen.

Answer 1

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write; 
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;

for(int currentInt=2; currentInt<=1000000; currentInt++) 
{check = false; 
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) 
        { c=num[arrayPrime];
            if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
                    break;}
               }


 if (!check)
    { e=currentInt;  
    if( currentInt!= 2 ) { 
    num[currentPrime]= currentInt;}
    currentPrime = currentPrime+1;}
    if(currentPrime==prime)
    {
    write<<e<<endl;
    break;}
    }
trial.close();
write.close();
return 0;
}

Dies ist die finalisierte Version Basis auf meinem ursprünglichen Code. Es funktioniert perfekt und wenn Sie den Bereich der Primzahlen erhöhen wollen einfach die Array-Nummer erhöhen. Danke für die Hilfe =)

Answer 2

Da Ihre Frage über die Programmierung ist nicht Mathematik, ich werde versuchen, meine Antwort zu halten auf diese Weise auch.

Der erste Blick des Codes macht mich fragen, was hier auf der Erde Sie tun ... Wenn Sie die Antworten zu lesen, werden Sie feststellen, dass einige von ihnen nicht, Ihren Code zu verstehen, störten, und einige Dump nur Ihren Code an einen Debugger und sehen, was los ist. Ist es, dass wir uns, dass ungeduldig? Oder ist es einfach, dass Ihr Code zu schwierig ist, für ein relativ einfaches Problem zu verstehen?

Ihr Code zu verbessern, versuchen Sie, sich einige Fragen stellen:

1. Was sind a, b, c, etc? Wäre es nicht besser zu geben, sinnvolle Namen?
2. Was genau ist Ihr Algorithmus? Können Sie sich einen deutlich geschrieben Absatz in englischer Sprache über aufschreiben, was Sie (in einer genauen Art und Weise) tun? Können Sie den Absatz in einer Reihe von Schritten ändern, die Sie geistig auf jede Eingabe durchführen und können sicher sein, dass es richtig ist?
3. Sind alle Schritte notwendig? Können wir kombinieren oder sogar einige von ihnen beseitigen?
4. Was sind die Schritte, die in Englisch auszudrücken sind einfach, aber erfordern, sagen wir, mehr als 10 Zeilen in C / C ++?
5. Ist Ihre Liste von Schritten irgendwelche Strukturen? Loops? Big (wahrscheinlich wiederholt) Stücke, die als einzelner Schritt mit Unterschritten umgesetzt werden können?

Nachdem Sie durch die Fragen haben, gingen, werden Sie wahrscheinlich haben einen übersichtlichen Pseudo-Code, der das Problem löst, das leicht zu erklären und zu verstehen. Danach können Sie Ihre Pseudo-Code in C / C ++ oder in der Tat eine allgemeine Zweck Sprache umzusetzen.

Answer 3

Es gibt zwei Ansätze zum Testen für primality möchten Sie vielleicht zu berücksichtigen:

1. Die Problemdomäne ist klein genug, dass über die Zahlen nur Looping, bis Sie die n-te Primzahl finden wahrscheinlich eine akzeptable Lösung und nimmt weniger wäre als ein paar Millisekunden abgeschlossen. Es gibt eine Reihe von einfachen Optimierungen Sie diesen Ansatz zum Beispiel machen können Sie nur testen müssen, um zu sehen, ob es um 2 einmal teilbar ist und dann haben Sie nur gegen die ungeraden Zahlen zu überprüfen und Sie nur Zahlen prüfen müssen kleiner oder gleich zur aquare Wurzel aus der Anzahl getestet.
2. Das Sieb des Eratosthenes sehr effektiv und einfach zu implementieren und unglaublich leicht auf der Mathematik Ende der Dinge.

Was, warum Sie Code abstürzt ich die Linie vermuten ändern, die liest

for( int d=0; d<=b; d++) 

for( int d=0; d<b; d++) 

wird das Problem beheben, weil Sie von einem potenziell nicht initialisierte Elemente des Arrays zu lesen versuchen, die wahrscheinlich Müll enthält.

Answer 4

Ich habe nicht auf den Code gesucht, aber Ihr Array muss groß genug sein, um alle Werte zu enthalten, die Sie darin gespeichert werden. sicherlich 100 ist für die meisten Eingaben für dieses Problem nicht genug sein werden.

z. dieser Code ..

int someArray[100];
someArray[150] = 10;

schreibt an einer Stelle groß als das Array (150> 100). Dies wird als eine Speicherüberschreibung bekannt. Je nachdem, was an dieser Speicherstelle sein passiert Ihr Programm kann sofort abstürzen, später oder überhaupt nicht.

Eine gute Praxis bei der Verwendung von Arrays someway zu behaupten, in ist, dass das Element, das Sie schreiben, innerhalb der Grenzen des Arrays ist. Oder verwenden Sie eine Array-Typ-Klasse, die diese Prüfung durchführt.

Für Ihr Problem wäre der einfachste Ansatz, die STL-Vektor-Klasse zu verwenden. Während Sie Elemente hinzufügen müssen (vector :: push_back ()) Sie können einen späteren Zugriff Elemente des Arrays Operator [] verwenden. Vector finden Sie auch die besten iterativen Leistung.

Hier ist ein Beispielcode die Anzahl der Zugabe von 0-100 auf einen Vektor und drucken dann. Hinweis in der zweiten Schleife wir die Anzahl der Elemente verwenden im Vektor gespeichert.

#include <vector> // std::vector

...

const int MAX_ITEMS = 100;

std::vector<int> intVector;

intVector.reserve(MAX_ITEMS); // allocates all memory up-front

// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
  intVector.push_back(i);  // this is how you add a value to a vector;
}

// print them
for (int i = 0; i < intVector.size(); i++)
{
  int elem = intVector[i]; // this access the item at index 'i'
  printf("element %d is %d\n", i, elem);
}

Answer 5

Ich versuche, meine funktionale Programmierung im Moment zu verbessern, so dass ich nur das Sieb schnell codiert werden. Ich denke, ich werde es hier posten. Wenn Sie noch lernen, Sie könnten es interessant finden, auch.

#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>

using namespace std;

class is_multiple : public binary_function<int, int, bool>
{
    public:
        bool operator()(int value, int test) const
        {
            if(value == test) // do not remove the first value
                return false;
            else
                return (value % test) == 0;
        }
};

int main() 
{
    list<int> numbersToTest;
    int input = 500;

    // add all numbers to list
    for(int x = 1; x < input; x++)
        numbersToTest.push_back(x);

    // starting at 2 go through the list and remove all multiples until you reach the squareroot
    // of the last element in the list
    for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
    {
        int tmp = *itr;
        numbersToTest.remove_if(bind2nd(is_multiple(), *itr));  
        itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator 
                                                                 // so find it again. kind of ugly
    }

    // output primes
    for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
        cout << *itr << "\t";

    system("PAUSE");

    return 0;
}

Jede Beratung, wie dies zu verbessern würde durch die Art und Weise willkommen.

Answer 6

Hier ist mein Code. Wenn auf einer großen Anzahl arbeiten, ist es sehr langsam! Es kann alle Primzahlen mit der Zahl Eingabe berechnen!

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int main()
{
    int m;
    int n=0;
    char ch;
    fstream fp;
    cout<<"What prime numbers do you want get within?  ";
    if((cin>>m)==0)
    {
                 cout<<"Bad input! Please try again!\n";
                 return 1;
    }
    if(m<2)
    {
        cout<<"There are no prime numbers within "<<m<<endl;
        return 0;
    }
    else if(m==2)
    {
        fp.open("prime.txt",ios::in|ios::out|ios::trunc);//create a file can be writen and read. If the file exist, it will be overwriten.
        fp<<"There are only 1 prime number within 2.\n";
        fp<<"2\n";
        fp.close();
        cout<<"Congratulations! It has worked out!\n";
        return 0;
    }
    else
    {
        int j;
        int sq;
        fp.open("prime.txt",ios::in|ios::out|ios::trunc);
        fp<<"2\t\t";
        n++;
        for(int i=3;i<=m;i+=2)
        {
            sq=static_cast<int>(sqrt(i))+1;
            fp.seekg(0,ios::beg);
            fp>>j;
            for(;j<sq;)
            {
                if(i%j==0)
                {
                    break;
                }

                else
                {
                    if((fp>>j)==NULL)
                    {
                        j=3;
                    }
                }
            }
            if(j>=sq)
            {
                fp.seekg(0,ios::end);
                fp<<i<<"\t\t";
                n++;
                if(n%4==0)
                    fp<<'\n';
            }
        }
        fp.seekg(0,ios::end);
        fp<<"\nThere are "<<n<<" prime number within "<<m<<".\n";
        fp.close();
        cout<<"Congratulations! It has worked out!\n";
        return 0;
    }
}

Answer 7

Zum einen würden Sie weniger Code haben (was immer eine gute Sache ist!), Wenn Sie keine Sonderfälle für 3 haben, 5 und 7.

Sie können aber auch den Sonderfall für 2, wenn Sie gerade eingestellt num [b] = 2 und nur Test auf Teilbarkeit durch Dinge in Ihrem Array vermeiden.

Answer 8

Es sieht aus wie, wie Sie die wichtigsten für () Schleife herumlaufen, wird der Wert von b erhöht.

Dann führt dies zu einem Absturz, weil Sie Speicher ab Ende Ihres Array zuzugreifen:

                for (int d = 0; d <= b; d++) {
                    c = num[d];

Ich glaube, Sie müssen den Algorithmus klarer im Kopf bekommen und dann den Code erneut nähern.

Answer 9

Ausführen von Code durch einen Debugger, habe ich festgestellt, dass es mit einer Gleitkomma-Ausnahme bei „if ((a % c) == 0)“ abstürzt. Der Grund dafür ist, dass man nicht alles in num initialisiert hat, so Sie tun „um eine% 0“.

Answer 10

  

Von dem, was ich weiß, in C / C ++ int ist ein 16-Bit-Typ, so dass Sie nicht eine Million darin passen können (maximal 2 ^ 16 = 32k). Versuchen Sie, und erklärt, „a“ so lange

Ich denke, der C-Standard sagt, dass int mindestens so groß wie short und höchstens so groß wie long.

In der Praxis int ist 4 Bytes, also Zahlen zwischen -2^31 und 2^31-1 halten kann.

Answer 11

Da dies für pädagogische Zwecke ist, würde ich vorschlagen, die Umsetzung das Sieb des Eratosthenes .

Answer 12

Dies sollte auch für Sie von Interesse sein: http://en.wikipedia.org/wiki/ Primality_test

Answer 13

for(int currentInt=2; currentInt<=1000000; currentInt++) 

{check = false;  // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )

for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.

{ c=num[arrayPrime];
        if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
                break;}  // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.


if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.

if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime. 

currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.

if(currentPrime==prime)
{
write<<e<<endl;
break;}           // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.

Danke für den Rat polythinker =)

Answer 14

Da Sie größere Primzahl Werte benötigen für später Fragen , ich schlagen Sie dreeves Beratung und tun ein Sieb folgen. Es ist ein sehr nützlicher Pfeil im Köcher haben.