Números primos programa

Question

Actualmente estoy probando algunas preguntas para practicar mis habilidades de programación.( No tomar en la escuela o nada todavía, autodidacta ) me encontré con este problema, que me obligó a leer en un número de un determinado archivo txt.Este número sería N.Ahora estoy supone para encontrar el N-ésimo número primo de N <= 10 000.Después de que me encuentre, estoy supone a imprimir a otro archivo txt.Ahora para la mayoría de las partes de la pregunta que yo soy capaz de entender y concebir un método para obtener N.El problema es que estoy usando un array para guardar encontrado previamente números primos con el fin de utilizarlos para comprobar en futuros números.Incluso cuando mi matriz de tamaño 100, mientras que la entrada de número entero era de aproximadamente < 15, el programa se bloquea.

#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 esta enteramente base en mi dummies guía y a mí mismo para hacer perdonar algunas código de la ineficiencia y la general novato-ness de mi algoritmo.También para grupos de hasta 15 muestra los números primos correctamente.

Podría alguien decirme cómo debo ir sobre la mejora de este código actual?Estoy pensando en usar un archivo txt en lugar de la matriz.Es eso posible?Cualquier ayuda es muy apreciada.

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

Esta es la base de la versión finalizada en 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 2

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

La primera mirada a tu código me hace preguntarme qué demonios estás haciendo aquí ... Si lees las respuestas, te darás cuenta de que algunas de ellas no se molestaron en entender tu código, y algunas simplemente lo volcaron. a un depurador y ver qué 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 claramente escrito en inglés sobre lo que estás haciendo (de manera exacta)? ¿Puede modificar el párrafo en una serie de pasos que puede realizar mentalmente en cualquier entrada y puede 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, por ejemplo, más de 10 líneas en C / C ++?
5. ¿Su lista de pasos tiene alguna estructura? Bucles? ¿Grandes (probablemente repetidos) fragmentos que se pueden poner como un solo paso con subpasos?

Después de haber examinado las preguntas, probablemente tendrá un pseudocódigo claramente establecido que resuelve 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, en cualquier lenguaje de propósito general.

Answer 3

Hay dos enfoques para probar la primalidad que tal vez desee considerar:

1. El dominio del problema es lo suficientemente pequeño como para que simplemente recorrer los números hasta encontrar el enésimo número primo sea una solución aceptable y tarde menos de unos pocos milisegundos en completarse. Hay varias optimizaciones simples que puede hacer a este enfoque, por ejemplo, solo necesita probar para ver si es divisible por 2 una vez y luego solo tiene que verificar los números impares y solo tiene que verificar números menores 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 ligero en matemáticas fin de las cosas.

En cuanto a por qué se bloquea el código, sospecho que cambia 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 desde un elemento de la matriz potencialmente no inicializado que probablemente contenga basura.

Answer 4

No he visto su código, pero su matriz debe ser lo suficientemente grande como para contener todos los valores que almacenará en ella. Ciertamente, 100 no será suficiente para la mayoría de las entradas para 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 sobrescribir 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 en el que está escribiendo está dentro de los límites de la matriz. O utilice una clase de tipo matriz que realice esta comprobación.

Para su problema, el enfoque más sencillo sería utilizar 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 código de muestra 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 5

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

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

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

#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

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

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

Answer 8

Parece que a medida que recorres el ciclo principal for (), el valor de b aumenta.

Entonces, esto se bloquea porque accedes a la memoria desde el final de tu matriz:

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

Creo que necesita tener el algoritmo más claro en su cabeza y luego abordar el código nuevamente.

Answer 9

Al ejecutar su código a través de un depurador, descubrí que se bloquea con una excepción de coma flotante en " if ((a % c) == 0) " ;. La razón de esto es que no ha inicializado nada en num, por lo que está haciendo & Quot; a% 0 & Quot ;.

Answer 10

Por lo que sé, en C/C++ int es un 16bit tipo por lo que no puede caber 1 millones (el límite es de 2^16=32k).Pruebe y declarar "a" como de largo

Creo que el C estándar dice que int es al menos tan grande como short y en la mayoría de los tan grande como long.

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

Answer 11

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

Answer 12

Esto también debería ser de su interés: 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.

Gracias por el consejo polythinker =)

Answer 14

Dado que necesitará valores de números primos mayores para preguntas posteriores , le sugiero que siga los consejos de dreeves y haga un tamiz. Es una flecha muy útil para tener en tu carcaj.