Programma numeri primi

Question

Attualmente sto provando alcune domande solo per esercitarmi nelle mie capacità di programmazione. (Non prenderlo a scuola o qualcosa del genere, autodidatta) Mi sono imbattuto in questo problema che mi ha richiesto di leggere un numero da un determinato file txt. Questo numero sarebbe N. Ora suppongo di trovare l'ennesimo numero primo per N & Lt; = 10 000. Dopo averlo trovato, suppongo di stamparlo su un altro file txt. Ora per la maggior parte delle parti della domanda sono in grado di capire e escogitare un metodo per ottenere N. Il problema è che sto usando un array per salvare i numeri primi trovati in precedenza in modo da usarli per verificare i numeri futuri. Anche quando il mio array aveva dimensioni 100, purché l'intero di input fosse approssimativamente & Lt; 15, il programma si arresta in modo anomalo.

#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;
}

Ho fatto tutto questo sulla base della mia guida sui manichini e di me stesso, quindi perdona un po 'di inefficienza del codice e una novità generale del mio algoritmo. Inoltre, per un massimo di 15, visualizza correttamente i numeri primi.

Qualcuno potrebbe dirmi come dovrei fare per migliorare questo codice attuale? Sto pensando di utilizzare un file txt al posto dell'array. È possibile? Qualsiasi aiuto è apprezzato.

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;
}

Questa è la base della versione finalizzata sul mio codice originale. Funziona perfettamente e se si desidera aumentare l'intervallo di numeri primi è sufficiente aumentare il numero di array. Grazie per l'aiuto =)

Answer 2

Poiché la tua domanda riguarda la programmazione piuttosto che la matematica, cercherò di mantenere la mia risposta anche in questo modo.

La prima occhiata al tuo codice mi fa chiedermi cosa diavolo stai facendo qui ... Se leggi le risposte, ti accorgerai che alcuni di loro non si sono preoccupati di capire il tuo codice, e altri hanno semplicemente scaricato il tuo codice a un debugger e vedere cosa sta succedendo. Siamo così impazienti? O è semplicemente che il tuo codice è troppo difficile da capire per un problema relativamente semplice?

Per migliorare il tuo codice, prova a porre alcune domande:

1. Cosa sono a, b, c, ecc.? Non sarebbe meglio dare nomi più significativi?
2. Qual è esattamente il tuo algoritmo? Puoi scrivere un paragrafo chiaramente scritto in inglese su ciò che stai facendo (in modo esatto)? Puoi modificare il paragrafo in una serie di passaggi che puoi eseguire mentalmente su qualsiasi input e puoi essere sicuro che sia corretto?
3. Sono necessari tutti i passaggi? Possiamo combinarne o addirittura eliminarne alcune?
4. Quali sono i passaggi che sono facili da esprimere in inglese ma richiedono, diciamo, più di 10 righe in C / C ++?
5. Il tuo elenco di passaggi ha delle strutture? Loops? Grandi pezzi (probabilmente ripetuti) che possono essere messi in un unico passaggio con passaggi secondari?

Dopo aver affrontato le domande, probabilmente avrai uno pseudo-codice ben definito che risolve il problema, che è facile da spiegare e capire. Successivamente puoi implementare il tuo pseudo-codice in C / C ++ o, di fatto, in qualsiasi linguaggio di uso generale.

Answer 3

Esistono due approcci per verificare la primalità che potresti prendere in considerazione:

1. Il dominio problematico è abbastanza piccolo che basta passare in rassegna i numeri fino a trovare l'ennesimo numero primo probabilmente sarebbe una soluzione accettabile e richiederebbe meno di qualche millisecondo per essere completato. Esistono alcune semplici ottimizzazioni che puoi apportare a questo approccio, ad esempio devi solo testare per vedere se è divisibile per 2 una volta e poi devi solo controllare contro i numeri dispari e devi solo controllare numeri inferiori o uguali alla radice acquare del numero in prova.
2. The Sieve of Eratosthenes è molto efficace e facile da implementare e incredibilmente leggero in matematica fine delle cose.

Per quanto riguarda il motivo per cui il codice si blocca, sospetto che cambi la riga che legge

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

a

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

risolverà il problema perché stai provando a leggere da un elemento potenzialmente non inizializzato dell'array che probabilmente contiene immondizia.

Answer 4

Non ho esaminato il tuo codice, ma l'array deve essere abbastanza grande da contenere tutti i valori che memorizzerai in esso. 100 non sarà certamente sufficiente per la maggior parte degli input per questo problema.

es. questo codice ..

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

Scrive in una posizione maggiore dell'array (150 > 100). Questo è noto come sovrascrittura della memoria. A seconda di ciò che è accaduto in quella posizione di memoria, il programma potrebbe bloccarsi immediatamente, successivamente o mai.

Una buona pratica quando si usano le matrici è di affermare in qualche modo che l'elemento su cui si sta scrivendo rientra nei limiti della matrice. Oppure usa una classe di tipo array che esegue questo controllo.

Per il tuo problema, l'approccio più semplice sarebbe usare la classe vettoriale STL. Mentre è necessario aggiungere elementi (vector :: push_back ()), è possibile accedere successivamente agli elementi utilizzando l'operatore dell'array []. Vector offre anche le migliori prestazioni iterative.

Ecco un codice di esempio per aggiungere i numeri 0-100 a un vettore e quindi stamparli. Nota nel secondo ciclo usiamo il conteggio degli oggetti memorizzati nel vettore.

#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

Al momento sto cercando di migliorare la mia programmazione funzionale, quindi ho appena codificato il setaccio rapidamente. Immagino che lo posterò qui. Se stai ancora imparando, potresti trovarlo anche interessante.

#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;
}

Qualunque consiglio su come migliorare questo sarebbe benvenuto comunque.

Answer 6

Ecco il mio codice. Quando si lavora su un numero elevato, è molto lento! Può calcolare tutti i numeri primi con il numero inserito!

#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

Per uno, avresti meno codice (che è sempre una buona cosa!) se non avessi casi speciali per 3, 5 e 7.

Inoltre, puoi evitare il caso speciale per 2 se hai appena impostato num [b] = 2 e hai verificato solo la divisibilità per cose nel tuo array.

Answer 8

Sembra che mentre cerchi il ciclo principale per (), il valore di b aumenta.

Quindi, si verifica un arresto anomalo perché si accede alla memoria dalla fine dell'array:

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

Penso che devi chiarire l'algoritmo nella tua testa e quindi avvicinarti di nuovo al codice.

Answer 9

Eseguendo il codice tramite un debugger, ho scoperto che si arresta in modo anomalo con un'eccezione in virgola mobile in " if ((a % c) == 0) " ;. Il motivo è che non hai inizializzato nulla in num, quindi stai facendo & Quot; a% 0 & Quot ;.

Answer 10

  

Da quello che so, in C / C ++ int è un tipo a 16 bit, quindi non puoi inserirne 1 milione (il limite è 2 ^ 16 = 32k). Prova a dichiarare & Quot; a & Quot; finché

Penso che lo standard C affermi che int è grande almeno quanto short e al massimo grande quanto long.

In pratica -2^31 è 4 byte, quindi può contenere numeri tra 2^31-1 e <=>.

Answer 11

Poiché questo è a fini pedagogici, suggerirei di implementare il setaccio di Eratostene .

Answer 12

Questo dovrebbe interessarti anche: 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.

Grazie per il consiglio polythinker =)

Answer 14

Poiché avrai bisogno di valori di numeri primi più grandi per domande successive , ti consiglio di seguire i consigli di dreeves e fare un setaccio. È una freccia molto utile da avere nella tua faretra.