Prime numbers between two large numbers?

Question

I wanted to find the prime numbers between two 13 digit numbers (1,000,000,000,000 and 1,000,000,100,000) ... I used something like unsigned long long or long long int and scanf with %llu and %lld but that does not work. How can I do this? I use the code like this:

int main()
{
  long long int n1, n2, i;
  int flag, j;
  printf("Enter two numbers (intervals): ");
  scanf("%lld %lld", &n1, &n2);
  printf("Prime numbers between %lld and %lld are: ", n1, n2);
  for(i=n1+1; i<n2; ++i)
  {
      flag=0;
      for(j=2; j<=i/2; ++j)
      {
        if(i%j==0)
        {
          flag=1;
          break;
        }
      }
      if(flag==0)
        printf("%lld ",i);
  }
  return 0;
}

Check out the [segmented sieve of Eratosthenes](http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes). — irrelephant, Nov 08 '14 at 05:10
You might want to include some newlines in some of the outputs. It isn't needed in the prompt (first `printf()`); most systems will ensure that standard output is flushed before reading anything. But the other print operations should include some newlines. Your algorithm is pretty inefficient. All else apart, 2 is the only even prime number. — Jonathan Leffler, Nov 08 '14 at 05:14
Try `%Ld` instead of `%lld` for `long long int` with `scanf()` — Dmitri, Nov 08 '14 at 05:20
@AnikIslamAbhi Yes, see [these stats](http://sweet.ua.pt/tos/goldbach/sieve_speed.pdf) from [this webpage](http://sweet.ua.pt/tos/software/prime_sieve.html). — irrelephant, Nov 08 '14 at 05:27
I don't think your code will work for 13 digit numbers but code that you posted is working pefectly!! check here : http://ideone.com/MSUKXK — Blackhat002, Nov 08 '14 at 07:03
regarding this line: scanf("%lld %lld", &n1, &n2); 1) the prior prompt does not indicate the two numbers need to be entered with an intervening space, not an intervening newline. 2) the returned value from scanf() needs to be checked to assure that both numbers were successfully converted. — user3629249, Nov 08 '14 at 08:49
need to validate the inputs to assure that n1 is actually less than n2. — user3629249, Nov 08 '14 at 08:51

score 1 · Accepted Answer · answered Nov 08 '14 at 18:04

j is an int, presumably a 32-bit type, while i is a long long int, presumably a 64-bit type. Since i is more than 2³², the value i/2 is more than the maximum value of the int type, which is 2³¹-1. Therefore the comparison j<=i/2 is always true, and the loop for(j=2; j<=i/2; ++j) never stops other than through the break inside the body. But this break is invoked only when j is a divisor of i, which never happens when i is prime.

If you change j to be a long long int, I think your program works, but it will take a very long time to go through the inner loop — n1/2 iterations. A simple improvement is to stop at the square root of i instead of half of i. This alone makes the program run at a decent pace on my machine.

You should add fflush(stdout); after each printf call, otherwise the output is buffered until the program exits. Alternatively, first call setbuf(stdout, NULL) to turn out output buffering.

This naive algorithm can definitely be improved: it repeats a lot of computations. You can store information in memory to avoid making the same tests over and over again; this is a time/memory trade-off. The sieve of Eratosthenes is a fairly simple algorithm that takes the trade-off to the other extreme: it maintains a table of sqrt(n2) bits, where the kth entry indicates whether k is prime. That would be workable here. You can also look at the open source BSD primes utility to see how they do it.

Prime numbers between two large numbers?

1 Answers1