Time limit exceeded when submitting

[leppyr64]

And what is a common property of all of the numbers that you will choose for M?

[mmm_sof]

I check for odd M only until the first M such that N%M = 0; but what from you say this is too much.. mmm sorry I don't get the point.

[mmm_sof]

ah perhaps, it's that all M must be prime?

[leppyr64]

That's one point! Since M will be prime, can you set a better upper bound for M than N/2?

[mmm_sof]

N/2-1 ...?

[leppyr64]

For N=323 would you choose M=19? It's less than N/2-1.

[mmm_sof]

No but I am already not choosing it; I'm returning false for M = 17.

I could save all prime numbers to some vector v and check if M != v[i] for all i before dividing for M.

[leppyr64]

I know you already choose M=17 but why do you choose that and not 19?

You could, and that's a good idea, but all of the primes up to 10^9 won't fit in an array. That's why you need to find the upper bound on M.

[mmm_sof]

when I write the for:

for(div = 3; div < n/2; div = div + 2)
{ if(n%div == 0) return false;}

the 'return' makes it leave the checkprime at M = 17 right? (so before 19)
It's not continuing with the for loop after it returns a false, right?

[leppyr64]

Yes, but you still need to reduce the upper limit for your variable div. (M)

[leppyr64]

N=37 is prime. What values do you need to check?

[mmm_sof]

I can check if the sum of the digits is a multiple of 3, or if the last two digits are a multiple of 4 (if I understand how to identify single digits in c++)

[mmm_sof]

For 37 I would check 37/2, then (7+3)/3
and then
5, 7, 11, 13, 15, 17.

Too many?

[leppyr64]

Of course it's too much. What's 37/17?

[mmm_sof]

ah I could consider only M up to sqrt(N). I tried but it still exceeds time limit.

[leppyr64]

Now go back to storing your primes in an array.

[mmm_sof]

ok, but I thought you said that's not possible for very large numbers. should I save primes in an array and print each time the array of the previous number plus new primes?

[leppyr64]

You can't store all of the primes up to 10^9, but ou can store all of the primes up to sqrt(10^9). That is all of the information that you need to know if a number is prime.

[mmm_sof]

ah, ok, I'll try. Thanks a lot for the help and the patience!

[mmm_sof]

Hi, this is the updated code; it still gives me the same error. I tried to divide only by the prime numbers already found.

#include <iostream>
#include <new>
using namespace std;
#include <stdio.h>
#include <math.h>
class getprime
{ int * x, * y;
  bool prime;
  //int div;                                                                                                
  public:
  bool checkprime(int, int*);
  int  printprime(int ,int);
};
bool getprime::checkprime(int n, int* z)
{ int div = 2;
  if(n==1) return false;
  else if(n<=3) return true;
  if(n%div==0) return false;
  for(int i = 0; i <= sqrt(n); i++)
    {
      if(z[i] != 0)
        {     if(n%(z[i]) == 0)  return false;
        }
    }
   return true;
}
int getprime::printprime(int x1, int x2)
{ prime = false;
  x = new (nothrow) int;
  x = &x1;
  int maxnum = sqrt(x2);
  y = new (nothrow) int[maxnum/2];
  *y = 0;
  int j = 0;
  while(*x<=x2)
    {
      prime = this->checkprime(*x,y);
      if(prime)
        {
          if(*x <= maxnum)
            { y[j] = *x;
              j++;
            }
          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;
}