Exercise from SPOJ - Prime Generator

[Petcheco]

Hello everyone. I saw a post of one of our friends here about a problem he found of the SPOJ website. So I went there to check it. I found it to be very cool; I started to do the exercises but when I got in the 2nd, a prime number generator, I got stuck. I did made the program and it works as it should, however, it's execution time is too long. So I'm coming here to ask for you to help me make my program more efficient. Here's my source code:

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

#define MAX_VALUE 1000000000
#define MAX_VALUE_FOR_N_AND_M 100000

fstream Arquivo("Arquivo.txt", ios::out);

int t = 0;
int m = 0;
int n = 0;
int p = 0;
bool Check_Sucessfull;

void Ask_Imputs(int&,int&,int);
void Check_Imput(int,int,bool&);
void Show_Primes(int,int, int);


void Ask_Imputs(int& m, int& n, int t)
{
    cin >> t;

    for (int a = 0; a < t; a++)
    {
        Check_Sucessfull = false;
        m = 0; n = 0;
        cin >> m >> n;
        printf("\n");
        Check_Imput(m,n,Check_Sucessfull);
        if (Check_Sucessfull == true)
        Show_Primes(m,n,p);
    }
}

void Check_Imput(int m, int n, bool& Check_Sucessfull)
{
    if (m >= 1 && m <= n && n <= MAX_VALUE && n-m <= MAX_VALUE_FOR_N_AND_M)
    Check_Sucessfull = true;
    else
    Check_Sucessfull = false;
}

void Show_Primes(int m, int n, int p)
{
    int Count;


    for (p = m; p <= n; p++)
    {
        Count = 0;
        if (p > 2 && p % 2 == 0)
        continue;
        else if (p > 3 && p % 3 == 0)
        continue;
        else if (p > 5 && p % 5 == 0)
        continue;
        if (p > 2)
        {
        for (int a = 1; a <= p; a++)
        {
        if (p % a == 0)
        {
            Count++;
             if (Count > 2)
        {
            continue;
        }
        }
        }
        }
        if (Count == 2 || p == 2)
        Arquivo << p << endl;
    }
    Arquivo << "\n";

}
int main()
{
    Ask_Imputs(m,n,t);
    Arquivo.close();
    return 0;

}

Thanks in advance, kind regards,
Petcheco

[NathanOliver]

you might want to look into the Sieve of Eratosthenes

[Petcheco]

Hello. Sorry for the late reply, I wasn't at home.

After seeing your answer, I went on Wikipedia and checked the Sieve of Eratosthenes' algorithm and implemented it on my code. It worked (I think so at least), however, when I submited it on the SPOJ, it gave me a Visual Time error. So I googled what could've happened and it seems that when imputed with bigger numbers, my program fails to allocate the needed memory. After I figured that out, I tried to use some modifiers (unsigned, long) and it still doesn't work. The problem could also be something related to nulling the pointers or the likes. I'll post my code now and hope for someone to be able to help me.

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

#define MAX_VALUE 1000000000
#define MAX_VALUE_FOR_N_AND_M 100000

fstream Arquivo("Arquivo.txt", ios::out | ios::app);

int t = 0;
int m = 0;
int n = 0;
int * Array_Primes;
bool Check_Sucessfull;

void Ask_Imputs(int&,int&,int);
void Check_Imput(int,int,bool&);
void Fill_Array_and_Show_it(int,int,int*);


void Ask_Imputs(int& m, int& n, int t)
{
    cin >> t;

    for (int a = 0; a < t; a++)
    {
        Check_Sucessfull = false;
        m = 0; n = 0;
        cin >> m >> n;
        Array_Primes = new int [(n - m)];
        printf("\n");
        Check_Imput(m,n,Check_Sucessfull);
        if (Check_Sucessfull == true)
        Fill_Array_and_Show_it(m,n,Array_Primes);
            delete [] Array_Primes;
             Array_Primes = NULL;
    }

}

void Check_Imput(int m, int n, bool& Check_Sucessfull)
{
    if (m >= 1 && m <= n && n <= MAX_VALUE && n-m <= MAX_VALUE_FOR_N_AND_M)
    Check_Sucessfull = true;
    else
    Check_Sucessfull = false;
}

void Fill_Array_and_Show_it(int m, int n, int *Array_Primes)
{


    for (int g = 2, h = 0; h < n - 1; g++, h++)
    {
       Array_Primes[h] = g;
    }

    for (int j = 2; j < sqrt(n); j++)
    {
        if (Array_Primes[j] == 0)
        continue;
        for (int a = 0; a < n - 1; a++)
        {
        if (Array_Primes[a] % j == 0 && Array_Primes[a] != j)
        Array_Primes[a] = 0;
        }
    }

      for (int p = 0; p < n - 1; p++)
    {
      if (Array_Primes[p] != 0)
     Arquivo << Array_Primes[p] << endl;
    }

}

int main()
{
    Ask_Imputs(m,n,t);
    Arquivo.close();
    return 0;

}

Thanks in advance,
Petcheco

[NathanOliver]

Are you supposed to write the answers to a file?

[Petcheco]

I suppose so. It helps with improving the speed of the output printing. But I supposed with had something to do with the pointers. Was I wrong?

[NathanOliver]

Do the requierments want the output to be to a file? I know with most online judges they want the output written to stdout. That could be what is giving you the error. Can you paste the instructions from the website to a post?

[Petcheco]

I can, although I think it's unnecessary because I tried to do it with cout and it didn't work either. So I suppose is something related to the pointers.

[NathanOliver]

Line 31 is not correct. If you are using a regular sieve you need to have all values from 2 to the highest number to check. on line 31 you only allocate enough space for n - m when you should allocate all the way to n.

[Petcheco]

So, I did what you said and it doesn't give a Runtime Error anymore. Thank you. But now, it's still taking to long. Is there anything else I can do to make my algorithm faster?

[NathanOliver]

what happenes if you change line 63 from

for (int a = 0; a < n - 1; a++)

to

for (int a = j; a < n - 1; a++)

[Petcheco]

Thanks, it does make it faster. But still not enough. I'll try to think something else too

[Petcheco]

Hello, with this code here:

    #include <iostream>
    #include <fstream>
    #include <math.h>
    using namespace std;

    #define MAX_VALUE 1000000000
    #define MAX_VALUE_FOR_N_AND_M 100000

    fstream Arquivo("Arquivo.txt", ios::out | ios::app);

    int t = 0;
    int m = 0;
    int n = 0;
    int * Array_Primes;
    bool Check_Sucessfull;

    void Ask_Imputs(int&,int&,int);
    void Check_Imput(int,int,bool&);
    void Fill_Array_and_Show_it(int,int,int*);


    void Ask_Imputs(int& m, int& n, int t)
    {
        cin >> t;

        for (int a = 0; a < t; a++)
        {
            Check_Sucessfull = false;
            m = 0; n = 0;
            cin >> m >> n;
            Array_Primes = new int [n];
            printf("\n");
            Check_Imput(m,n,Check_Sucessfull);
            if (Check_Sucessfull == true)
            Fill_Array_and_Show_it(m,n,Array_Primes);
                delete [] Array_Primes;
                 Array_Primes = NULL;
        }

    }

    void Check_Imput(int m, int n, bool& Check_Sucessfull)
    {
        if (m >= 1 && m <= n && n <= MAX_VALUE && n-m <= MAX_VALUE_FOR_N_AND_M)
        Check_Sucessfull = true;
        else
        Check_Sucessfull = false;
    }

    void Fill_Array_and_Show_it(int m, int n, int *Array_Primes)
    {


        for (int g = 2, h = 0; h < n - 1; g++, h++)
        {
           Array_Primes[h] = g;
        }

        for (int j = 2; j < sqrt(n); j++)
        {
            if (Array_Primes[j] == 0)
            continue;
            for (int a = j; a < n - 1; a++)
            {
            if (Array_Primes[a] % 2 == 0 && Array_Primes[a] != 2)
            Array_Primes[a] = 0;
            if (Array_Primes[a] % j == 0 && Array_Primes[a] != j)
            Array_Primes[a] = 0;
            }
        }

          for (int p = 0; p < n - 1; p++)
        {
          if (Array_Primes[p] != 0)
         Arquivo << Array_Primes[p] << endl;
        }

    }

    int main()
    {
        Ask_Imputs(m,n,t);
        Arquivo.close();
        return 0;

    }

it tooked 66.6 seconds to calculate all prime numbers from 1 to 10000000 (In order to do that I changed the Check_Imput function to set the Check_Sucessfull to always true due to the restrain it had regarding the difference between m and n). It's fast (I think) and I'm kind of proud of myself (with your help of course), however, it still not enough for the Website and frankly, I've run out of ideas regarding how to improve it's speed, :(. So here I am, again, asking for help. I hope you understand.

Regards,
Petcheco

[CGSMCMLXXV]

As far as I could understand your code, you are bound to run into two problems:

1. redundancy (at every new iteration over t, you compute again the set of values which were computed in previous iteration);
2. crash (setting n too high is bound to require more memory than you can allocate).

Just to explain a bit the first problem. Take m, n and t, for example. They should split your array into t chunks, with m the starting value and n the final value in the chunk, according to your Check_Imput function. Still, in both Ask_Imputs and Fill_Array_and_Show_it functions, you iterate from 0 to n-1 all the time (you don't use m as initial value for your loop).

Please, correct me if I understood your code wrongly.

[NathanOliver]

Why do you have 2 if's in your for loop on lines 63-69?

[Petcheco]

Hello. Well, on the Ask_Imputs, I don't iterate until N because what I want to do is iterate until T, which is the number of test cases. As for the Fill_Array_and_Show_it, when I tried to change it, it gave me the wrong answers. So here's my code, which now, is doing 1 - 10000000 in 36 seconds.

    #include <iostream>
    #include <fstream>
    #include <math.h>
    using namespace std;

    #define MAX_VALUE 1000000000
    #define MAX_VALUE_FOR_N_AND_M 100000

    fstream Arquivo("Arquivo.txt", ios::out | ios::app);

    int t = 0;
    int m = 0;
    int n = 0;
    int * Array_Primes;
    bool Check_Sucessfull;

    void Ask_Imputs(int&,int&,int);
    void Check_Imput(int,int,bool&);
    void Fill_Array_and_Show_it(int,int,int*);


    void Ask_Imputs(int& m, int& n, int t)
    {
        cin >> t;

        for (int a = 0; a < t; a++)
        {
            Check_Sucessfull = false;
            m = 0; n = 0;
            cin >> m >> n;
            Array_Primes = new int [n + 2];
            printf("\n");
            Check_Imput(m,n,Check_Sucessfull);
            if (Check_Sucessfull == true)
            Fill_Array_and_Show_it(m,n,Array_Primes);
                delete [] Array_Primes;
                 Array_Primes = NULL;
        }

    }

    void Check_Imput(int m, int n, bool& Check_Sucessfull)
    {
        /*if (m >= 1 && m <= n && n <= MAX_VALUE && n-m <= MAX_VALUE_FOR_N_AND_M)
        Check_Sucessfull = true;
        else */
        Check_Sucessfull = true;
    }

    void Fill_Array_and_Show_it(int m, int n, int *Array_Primes)
    {


        for (int g = 2; g < n + 1; g++)
        {
           Array_Primes[g] = g;
        }

        for (int j = 2; j < sqrt(n+1); j++)
        {
            if (Array_Primes[j] == 0)
            continue;
            for (int a = j; a < n + 1; a++)
            {
            if (Array_Primes[a] % j == 0 && Array_Primes[a] != j)
            Array_Primes[a] = 0;
            }
        }

          for (int p = 2; p < n + 1; p++)
        {
          if (Array_Primes[p] != 0)
         Arquivo << Array_Primes[p] << endl;
        }

    }

    int main()
    {
        Ask_Imputs(m,n,t);
        Arquivo.close();
        return 0;

    }

Regards,
Petcheco

P.S.: Nathan, I changed that back to normal. I had it because I was testing some changes but I forgot to remove it before pasting it here.

[NathanOliver]

Here is some code that says it will do it in 3.9 seconds. You can take a look at at and see how it works. You Might want to do some goole searches as well for faster algo's. I know there a few really good post on this site that have some very nice algo's

[vijayan121]

Though n is very large, n-m is quite small (n-m) < 100000.
You do not need a full sieve; a partial sieve with a size of n-m+1 would suffice.

#include <iostream>
#include <vector>
#include <cmath>

// copy all prime numbers between m and n to stm
void copy_primes_between( int m, int n, std::ostream& stm )
{
    // invariant: m >1, m < n , n <= 1000000000
    // invariant: (n-m) <= 100000

    // generate a partial sieve from m to n

    std::vector<bool> sieve( n-m+1, true ) ;

    // knock off all the even numbers
    for( int i = m%2 ? m+1 : m ; i <= n ; i += 2 ) sieve[i-m] = false ;
    if( m == 2 ) sieve[0] = true ;

    // and then multiples of odd numbers
    const int rootn = std::sqrt(n) + 1 ;
    for( int p = 3 ; p <= rootn ; p += 2 )
      for( int i = (m/p)*p ; i<=n ; i += p ) if( i != p && i>=m ) sieve[i-m] = false ;

    // write the prime numbers them out
    for( std::size_t i = 0 ; i < sieve.size() ; ++i )
      if( sieve[i] ) stm << m+i << '\n' ;

}

int main()
{
    std::cout.sync_with_stdio(false) ;
    copy_primes_between( 990000000, 990000100, std::cout ) ;
}

[Petcheco]

But everytime time I try to start my loops with the value of m instead of 2, the values come all messed up. The logic ceases to work.