c++ - rango - Programa de números primos

programa en c que calcule numeros primos

Question

Actualmente estoy probando algunas preguntas solo para practicar mis habilidades de programación. (No lo tomo en la escuela ni nada, autodidacta) Me encontré con este problema que requería que leyera un número de un archivo txt dado. Este número sería N. Ahora se supone que debo encontrar el N-ésimo número primo para N <= 10 000. Después de encontrarlo, se supone que debo imprimirlo en otro archivo txt. Ahora, para la mayoría de las partes de la pregunta, puedo entender y diseñar un método para obtener N. El problema es que estoy usando una matriz para guardar números primos previamente encontrados para usarlos para verificar contra números futuros. Incluso cuando mi array era del tamaño 100, siempre y cuando el entero de entrada fuera aproximadamente <15, el programa falla.

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

Hice esto completamente basado en mi guía de dummies y en mí mismo, así que perdonaré la ineficacia de algunos códigos y la novación general de mi algoritmo. También para hasta 15 muestra los números primos correctamente.

¿Alguien podría decirme cómo debo mejorar este código actual? Estoy pensando en usar un archivo txt en lugar de la matriz. ¿Es eso posible? Cualquier ayuda es apreciada.

Answer 1

Por lo que sé, en C / C ++ int es un tipo de 16 bits, por lo que no caben 1 millón en él (el límite es 2 ^ 16 = 32k). Intenta y declara "a" siempre que

Creo que el estándar C dice que int es al menos tan grande como short y al menos tan long como long .

En la práctica, int tiene 4 bytes, por lo que puede contener números entre -2^31 y 2^31-1 .

Answer 2

Como necesitará valores más grandes de números primos para preguntas posteriores , le sugiero que siga los consejos de Dreeves y haga un colador. Es una flecha muy útil para tener en su carcaj.

Answer 3

Como su pregunta es sobre programación en lugar de matemáticas, intentaré mantener mi respuesta de esa manera también.

La primera mirada a su código me hace preguntarme qué demonios está haciendo aquí ... Si lee las respuestas, se dará cuenta de que algunos de ellos no se molestaron en comprender su código, y algunos simplemente descargan su código a un depurador y mira lo que está pasando ¿Es que somos tan impacientes? ¿O es simplemente que su código es demasiado difícil de entender para un problema relativamente fácil?

Para mejorar su código, intente hacerse algunas preguntas:

1. ¿Qué son a , b , c , etc.? ¿No sería mejor dar nombres más significativos?
2. ¿Cuál es exactamente tu algoritmo? ¿Puedes escribir un párrafo escrito claramente en inglés sobre lo que estás haciendo (de manera exacta)? ¿Puedes modificar el párrafo en una serie de pasos que puedes llevar a cabo mentalmente en cualquier entrada y puedes estar seguro de que es correcto?
3. ¿Son necesarios todos los pasos? ¿Podemos combinar o incluso eliminar algunos de ellos?
4. ¿Cuáles son los pasos que son fáciles de expresar en inglés pero requieren, digamos, más de 10 líneas en C / C ++?
5. ¿Su lista de pasos tiene alguna estructura? Loops? ¿Grandes fragmentos (probablemente repetidos) que se pueden poner como un solo paso con subpasos?

Una vez que haya realizado las preguntas, probablemente tenga un pseudocódigo claramente establecido que resuelva el problema, que es fácil de explicar y comprender. Después de eso, puede implementar su pseudocódigo en C / C ++ o, de hecho, cualquier lenguaje de propósito general.

Answer 4

Dado que esto es para fines pedagógicos, sugeriría implementar el Tamiz de Eratóstenes .

Answer 5

Ejecutando su código a través de un depurador, he encontrado que se bloquea con una excepción de punto flotante en " if ((a % c) == 0) ". La razón de esto es que no has inicializado nada en num, por lo que estás haciendo "un% 0".

Answer 6

Esto también debería ser de su interés: http://en.wikipedia.org/wiki/Primality_test

Answer 7

Estoy tratando de mejorar mi programación funcional en este momento, así que simplemente codifiqué el tamiz rápidamente. Me imagino que lo publicaré aquí. Si todavía estás aprendiendo, puede que te resulte interesante también.

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

Cualquier consejo sobre cómo mejorar esto sería bienvenido por cierto.

Answer 8

Hay dos enfoques para probar la primalidad que quizás desee considerar:

1. El dominio del problema es lo suficientemente pequeño como para que el simple hecho de pasar los números hasta que encuentre el Nth prime sea probablemente una solución aceptable y tome menos de unos pocos milisegundos en completarse. Hay varias optimizaciones simples que puede realizar en este enfoque, por ejemplo, solo necesita probar para ver si es divisible por 2 una vez y luego solo tiene que comparar con los números impares y solo debe verificar los números menores que o iguales a la raíz cuadrada del número que se está probando.
2. El tamiz de Eratóstenes es muy efectivo y fácil de implementar e increíblemente liviano en el aspecto matemático.

En cuanto a por qué tu código se bloquea, sospecho que cambiar la línea que dice

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

a

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

solucionará el problema porque está intentando leer un elemento potencialmente no inicializado de la matriz que probablemente contenga basura.

Answer 9

No he revisado su código, pero su matriz debe ser lo suficientemente grande como para contener todos los valores que almacenará en ella. 100 ciertamente no será suficiente para la mayoría de los aportes a este problema.

Por ejemplo, este código ...

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

Escribe en una ubicación más grande que la matriz (150> 100). Esto se conoce como sobrescritura de memoria. Dependiendo de lo que sucedió en esa ubicación de memoria, su programa puede bloquearse inmediatamente, más tarde o nunca.

Una buena práctica al usar matrices es afirmar de alguna manera que el elemento al que está escribiendo está dentro de los límites de la matriz. O use una clase tipo array que realice esta comprobación.

Para su problema, el enfoque más fácil sería usar la clase de vector STL. Si bien debe agregar elementos (vector :: push_back ()), puede acceder posteriormente a los elementos utilizando el operador de matriz []. Vector también le dará el mejor rendimiento iterativo.

Aquí hay un ejemplo de código para agregar los números 0-100 a un vector y luego imprimirlos. Tenga en cuenta que en el segundo ciclo usamos el recuento de elementos almacenados en el vector.

#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 10

Parece que a medida que avanzas por el ciclo principal de (), el valor de b aumenta.

Entonces, esto resulta en un bloqueo porque accede a la memoria desde el final de su matriz:

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

Creo que debes obtener el algoritmo más claro en tu cabeza y luego abordar el código nuevamente.

Answer 11

Por un lado, tendrías menos código (¡lo cual siempre es bueno!) Si no tienes casos especiales para 3, 5 y 7.

Además, puede evitar el caso especial para 2 si solo establece num [b] = 2 y solo prueba la divisibilidad por cosas en su matriz.

Answer 12

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

Esta es la versión finalizada de mi código original. Funciona perfectamente y si desea aumentar el rango de números primos simplemente aumente el número de matriz. Gracias por la ayuda =)

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.

Gracias por el consejo polythinker =)

Answer 14

Aquí está mi código. Cuando trabajas en un gran número, ¡es muy lento! ¡Puede calcular todos los números primos con el número que ingresó!

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