programa de números primos

Question

Atualmente estou tentando algumas perguntas apenas para praticar minhas habilidades de programação. (Não tomá-lo na escola ou nada ainda, autodidata) me deparei com este problema que me obrigado a ler em um número a partir de um determinado arquivo txt. Este número seria N. Agora eu sou supor para encontrar o número primo Nth para N <= 10 000. Depois que eu encontrá-lo, eu sou supor para imprimi-lo para outro arquivo txt. Agora, para a maioria das partes da questão que eu sou capaz de entender e elaborar um método para obter N. O problema é que eu estou usando uma matriz para salvar anteriormente encontrados números primos, de modo a usá-los para verificar contra números futuros. Mesmo quando minha matriz era do tamanho 100, enquanto o número inteiro de entrada foi de cerca de <15, o programa deixa de funcionar.

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

Eu fiz esta base inteiramente em meu guia de manequins e mim para fazer perdoar alguma ineficiência código e novato-ness geral do meu algoritmo. Também para até 15 ele exibe os números primos corretamente.

Alguém poderia me dizer como eu deveria ir sobre como melhorar este código atual? Estou pensando em usar um arquivo txt no lugar da matriz. Isso é possível? Qualquer ajuda é 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 é a base versão finalizada no meu código original. Ele funciona perfeitamente e se você quiser aumentar a gama de números primos simplesmente aumentar o número da matriz. Obrigado pela ajuda =)

Answer 2

Uma vez que sua pergunta é sobre a programação em vez de matemática, vou tentar manter a minha resposta dessa forma também.

A primeira vista do seu código faz-me pergunto o que diabos você está fazendo aqui ... Se você ler as respostas, você vai perceber que alguns deles não se preocupou em entender o seu código, e alguns simplesmente despejar seu código a um depurador e ver o que está acontecendo. Será que estamos que impaciente? Ou é simplesmente que o seu código é muito difícil de entender para um problema relativamente fácil?

Para melhorar o seu código, tente perguntar a si mesmo algumas perguntas:

1. Quais são a, b, c, etc? Não seria melhor dar nomes mais significativos?
2. O que exatamente é o seu algoritmo? você pode escrever um parágrafo claramente escrito em Inglês sobre o que você está fazendo (de forma exata)? você pode modificar o parágrafo em uma série de passos que você pode mentalmente realizar em qualquer entrada e pode ter certeza que ele está correto?
3. Tem todas as medidas necessárias? podemos combinar ou mesmo eliminar alguns deles?
4. Quais são os passos que são fáceis de expressar em Inglês, mas exigem, por exemplo, mais de 10 linhas em C / C ++?
5. A sua lista de passos tem nenhum estruturas? Rotações? Big (provavelmente repetida) pedaços que podem ser colocados como um único passo com sub-passos?

Depois de atravessar as perguntas, você provavelmente terá um pseudo-código claramente definidos que resolve o problema, que é fácil de explicar e entender. Depois que você pode implementar o seu pseudo-código em C / C ++, ou, de fato, qualquer linguagem de propósito geral.

Answer 3

Existem duas abordagens para testar para primalidade que você pode querer considerar:

1. O domínio do problema é pequeno o suficiente para que apenas looping sobre os números até encontrar o primeiro-Nth provavelmente seria uma solução aceitável e leva menos de alguns milissegundos para ser concluído. Há uma série de otimizações simples que você pode fazer com esta abordagem, por exemplo, você só precisa de teste para ver se ele é divisível por 2 uma vez e, em seguida, você só tem que verificar contra os números ímpares e você só tem que verificar os números inferiores ou iguais à raiz aquare do número a ser testado.
2. O Crivo de Eratóstenes é muito eficaz e fácil de implementar e incrivelmente luz sobre a matemática fim das coisas.

Quanto ao porquê de você código está falhando eu suspeito mudando a linha que lê

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

para

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

vai resolver o problema porque você está tentando ler a partir de um elemento potencialmente não inicializada da matriz que provavelmente contém lixo.

Answer 4

Eu não olhei para seu código, mas a sua matriz deve ser grande o suficiente para conter todos os valores que você irá armazenar nele. 100 certamente não vai ser suficiente para a maioria de entrada para este problema.

por exemplo. este código ..

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

Grava para um local grande do que a matriz (150> 100). Isto é conhecido como uma substituição de memória. Dependendo do que passou a ser no local de memória que o programa pode falhar imediatamente, mais tarde ou nunca.

Uma boa prática quando usando matrizes é afirmar de alguma forma que o elemento que você está escrevendo está dentro dos limites da matriz. Ou usar uma classe do tipo matriz que executa esta verificação.

Para o seu problema a abordagem mais fácil seria usar a classe STL vector. Enquanto você deve adicionar elementos (vector :: push_back ()), você pode elementos mais tarde de acesso que utilizam o operador array []. Vector também lhe dará o melhor desempenho iterativo.

Aqui está um código de exemplo de adicionar os números 0-100 para um vetor e, em seguida, imprimi-los. Nota no segundo laço usamos a contagem de itens armazenados no vetor.

#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

Eu estou tentando melhorar a minha programação funcional no momento, então eu só codificado-se a peneira rapidamente. Eu acho que eu vou postá-lo aqui. Se você ainda está aprendendo, você pode achar que é interessante, também.

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

Qualquer conselhos sobre como melhorar esta seria bem-vinda pelo caminho.

Answer 6

Aqui está o meu código. Ao trabalhar em um número grande, é muito lento! Pode calcular todos os números primos com o número que você entrada!

#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 um lado, você teria menos código (que é sempre uma coisa boa!) Se você não tem casos especiais para 3, 5 e 7.

Além disso, você pode evitar o caso especial para 2 se você só conjunto num [b] = 2 e único teste de divisibilidade por coisas em sua matriz.

Answer 8

Parece que você vá ao redor do circuito principal para (), o valor de B aumenta.

Então, isso resulta em um acidente porque você acessar a memória do final de sua matriz:

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

Eu acho que você precisa para obter o algoritmo mais clara em sua cabeça e, em seguida, abordar o código novamente.

Answer 9

Executando o seu código através de um depurador, eu descobri que ele trava com uma exceção de ponto flutuante com "if ((a % c) == 0)". A razão para isso é que você não inicializou nada em num, assim que você está fazendo "um% 0".

Answer 10

Pelo que eu sei, em C / C ++ int é um tipo de 16 bits para que você não pode caber 1 milhão nele (o limite é 2 ^ 16 = 32k). Experimente e declarar "a" contanto

Eu acho que o padrão C diz que int é pelo menos tão grande quanto short e no máximo tão grande quanto long.

Na prática int é de 4 bytes, então ele pode conter números entre -2^31 e 2^31-1.

Answer 11

Uma vez que este é para fins pedagógicos, gostaria de sugerir a implementação o Crivo de Eratóstenes .

Answer 12

Este também deve ser de seu interesse: 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.

Obrigado pela polythinker aconselhamento =)

Answer 14

Uma vez que você terá maiores valores de número primo para perguntas posteriores , I sugiro que você siga o conselho dreeves, e fazer uma peneira. É uma seta muito útil para ter em sua aljava.