Prime problem

[abachler]

Well, in any case, i optimized the output and it snuck in at 4.6 seconds, so I can walk away (i.e. run screaming) from this problem and move on to the next one. I actually do appreciate your help and patience on this problem. Ultimately I threw out doing any kind of seive and just checked each number in the range by marking as composite any number that taken modulus a prime less than or equal to its root resulted in 0.

While this is technically slower than other methods, it does in fact produce fast enough results.

I am curious though if there is some other method besides printing it to the console that is acceptable? Would it be possible to print it to a specific output file directly from within my program, which should eb much faster than usign printf(). It would be helpful on future problems.

As for the prined output, its because when run in debug mode (i.e. with _WIN32 defined) instead fo takign input from teh console, it randomly generates 10 sets of ranges, so the last one may be lower than the others.

[TripleM_sof]

Right. So that explains why you thought your program ran fast. rand() only returns a number up to 32768, so you were only testing your program on very very small inputs. If you had gotten rid of the debugging and just entered the largest possible test case, you would have found that it was running far too slow - a proper sieve would make it run at exactly the same speed as the 1-100000 case. Testing on handpicked test cases is much better than testing on random ones.

In terms of the program itself, you just print to stdout - I was meaning in terms of testing your program. The issue is not that of the outputting taking time - it is that displaying the output takes a long time. If you open up a command prompt, and run your program but directed (via the command prompt) to an output file in the way I mentioned, you will see how long the code actually takes to run, not counting the displaying of the output which isn't part of the program.

For your interest, I've PMed you how to fix your code so it runs fast enough.

[phobosq_sof]

I, too, have a problem with PRIME1 - I am quite sure that my program runs fine but there's something wrong with output. Take a look at the code:

#include <stdio.h>
#include <math.h>
unsigned long primes[20000];
int pc = 0;
void primeHigh(unsigned long a, unsigned long b);
void generatePrimes();
void primeHigh(unsigned long a, unsigned long b)
{
  unsigned long i;
  int j, flag = 1;
  int initial = 1;
  if (b <= 32000)
  {
    j = 0;
    while(primes[j] < a) j++;
    while(primes[j] <= b && j < pc)
{
  if (initial)
  {
     printf("%ld", primes[j++]);
     initial = 0;
  }
  else
     printf("\n%ld", primes[j++]);
}
  }
  else if (a < 32000 && b > 32000)
  {
       primeHigh(a, 32000);
       primeHigh(32000, b);
  }
  else
  {
    for(i = a; i <= b; i++)
    {
      if (!(i % 2)) continue;
      else
      {
        for (j = 0; (j < pc) && (primes[j] * primes[j] <= i); j++)
        {
          if (!(i % primes[j]))
          {
            flag = 0;
            break;
          }  
        }
        if (flag)
    {
          if (initial)
          {
             printf("%ld", i);
             initial = 0;
          }
          else
             printf("\n%ld", i);
    }
    else
        flag = 1;
  }
}
  }
}
void generatePrimes()
{
  unsigned long i, j, flag = 1;
  primes[pc++] = 2;
  for (i = 3; i <= 32000; i++)
  {
    for (j = 0; (j < pc) && (primes[j] * primes[j] <= i); j++)
    {
      if (!(i % primes[j]))
      {
        flag = 0;
        break;
      }
    }
    if (flag)
  primes[pc++] = i;
else
  flag = 1;
  }
}
int main()
{
  int t; /* ile jest testow */
  unsigned long mn[20]; /* granice gora dol - parzyste dolne, nieparzyste gorne*/
  unsigned long i;
/*** init ***/
  scanf("%d", &t);
  for (i = 0; i < t; i++)
    scanf("%ld %ld", &(mn[2 * i]), &(mn[(2 * i) + 1]));
  generatePrimes();
/*** main loop ***/
  for (i = 0; i < t; i++)
  {
    primeHigh(mn[2 * i], mn[(2 * i) + 1]);
    if (i != t - 1)
       printf("\n\n");
  }
  return 0;
}

Can someone confirm that it runs OK?