Time limit exceeded when submitting

[prodigyaj]

Hello all ,
in reference to the Prime generator problem (PRIME1) , my code takes 0.54 sec for 10 test cases of worst case inputs 999900000 1000000000, still the system says time limit exceeded ,when a max of 6s is alloted , any reasons ?
If anyone willing to help i will post my code in my next post !!!

AJ

[prodigyaj]

solved !!

[alizadeh_sof]

hello could you tell me how it solved? I have this problem too,please help me.tnks

[mmm_sof]

Hi,
I am not sure this is the right place to post this, but I couldn't find a better one.
If I run the following code for prime generator I get the error time limit exceeded. Could anyone explain me why?
If I run it on a terminal it seems to be ok, though I am sure there are much smarter ways to do it.
Thanks a lot
m.

include

using namespace std;

include

class getprime
{ int * x;
int div;
public:
int printprime(int ,int);
};

int getprime::printprime(int n1, int n2)
{ bool prime(true);
x = new int [n2];
x = & n1;
while(*x <= n2)
{
if(n1 == 1){n1++;}
{
div = n1;
do{ if((*x)%(div-1) != 0)
{ prime = true;
}
else
{prime = false ;}
div--;
}while(div != 2 && prime);
if(prime)
printf("%d \n",*x); // PRIMES between n1 and n2
(*x)++;
}
}
// delete x;
}

int main()
{ int i,tcases; // number of cases to analyze
int *cases, *x;
getprime primeobj;
cin >> tcases;
if(tcases >10) return 1;
cases = new (nothrow) int[2];
for(i=0;i { cin >> cases[0];
cin >> cases[1];
cout << cases[0] << " " << cases[1] << endl;
primeobj.printprime(cases[0],cases[1]);
cout << "\n";
}
//delete [] cases;
}

[leppyr64]

viewtopic.php?f=3&t=5516

[mmm_sof]

Thanks, I had read that post already: I removed cin/cout, I tried with large values on shell and it works, I searched in the forum and I found this post. I still can't find the problem though.

[mmm_sof]

just to be precise, the updated code (which still doesn't work for the same problem) is:

include

using namespace std;

include

class getprime
{ int * x;
int div;
public:
int printprime(int ,int);
};

int getprime::printprime(int n1, int n2)
{ bool prime(true);
// if(n2 == 1)
// {return 1;}
x = new int [n2];
x = & n1;
while(*x <= n2)
{
if(n1 == 1){n1++;}
{
div = n1;
do{ if((*x)%(div-1) != 0)
{ prime = true;
}
else
{prime = false ;}
div--;
}while(div != 2 && prime);
if(prime)
printf("%d \n",*x); // PRIMES between n1 and n2
(*x)++;
}
}
// delete x;
}

int main()
{ int i,tcases; // number of cases to analyze
int *cases, *x;
getprime primeobj;

scanf("%d", &tcases);
if(tcases >10) return 1;
cases = new (nothrow) int[2];
for(i=0;i { scanf("%d",&cases[0]);
scanf("%d", &cases[1]);
printf("%d %d \n",cases[0],cases[1]);
primeobj.printprime(cases[0],cases[1]);
printf("\n");
}
//delete [] cases;
}

[leppyr64]

You still havent posted your code using code tags.

Your method of finding whether a number is prime or not is too slow. What can you tell me about a number that is NOT prime?

[mmm_sof]

Hi,
I changed the code, this version should be faster but it still gives the same error.
thanks for your help.

#include <iostream>
#include <new>
using namespace std;
#include <stdio.h>
class getprime
{ int * x;
  bool prime;
  //int div;                                                                                                            
  public:
  bool checkprime(int);
  int  printprime(int ,int);
};                                                      
bool getprime::checkprime(int n)
{ int div = 2;
  if(n==1) return false;
  else  if(n<=3) return true;
  if(n%div==0) return false;
   for(div = 3; div < n/2; div = div + 2)
     { if(n%div == 0)  return false;}
   return true;
}
int getprime::printprime(int x1, int x2)
{ prime = false;
  x = new (nothrow) int;
  x = &x1;
  while(*x<=x2)
    {
      prime = this->checkprime(*x);
      if(prime) printf("%d \n", *x);
      (*x)++;
    }
}
int main()
{ int i,tcases;  // number of cases to analyze                                                                          
  int *cases, *x;
  getprime primeobj;
  scanf("%d", &tcases);
  if(tcases >10) return 1;
  cases = new (nothrow) int[2];
  for(i=0;i<tcases;i++)
    { scanf("%d",&cases[0]);
      scanf("%d", &cases[1]);
      printf("%d %d \n",cases[0],cases[1]);
      //      while(cases[0]<=cases[1])                                                                                 
      { primeobj.printprime(cases[0],cases[1]);
          //      cases[0]++;                                                                                           
        }
      printf("\n");
    }
  delete x;
}

[leppyr64]

For EVERY number n in the range a to b you are iterating up to n/2. For the maximum sized range, with a and b being the largest possible, that is an extreme amount of operations. You need to answer my question.

What can you tell me about a number that is NOT prime?

[mmm_sof]

mmm, maybe for every non prime number I should already exclude its multiples smaller than n2?

[leppyr64]

Give me the definition of number that is not prime.

[mmm_sof]

perhaps I should keep in memory the prime numbers already found and check only from the highest one on..?

[mmm_sof]

A number N is not prime if it exists a number M < N and M neq 1, such that N%M = 0

[leppyr64]

Can you reduce the definition of M to something more detailed than "a number less than N"?

[mmm_sof]

an int > 1 such that.. ?

[leppyr64]

If N=36 would you worry about M=6? Or M=18? Why not?

[mmm_sof]

because they are multipoles of 2 and 3. However, in my code I already return the first time it encounters a number M such that N%M = 0 (at least that's what I think it's doing); so if I insert 36 it only checks if 36%2 = 0 and then it already concludes it's not prime. It doesn't check for 6 or 18, not even for 3.

[mmm_sof]

so in my code I am already checking first if it's even or odd, and then I go to the for loop (from div = 3 on) only if it's odd.

[leppyr64]

How about 215441? What are you going to choose for M? Do you really need to check all the way up to N/2?