CODEWITHSUNDEEP
c
Proloy
Proloy

Reputation: 363

Prime numbers between two large numbers?

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;
}

Upvotes: 1

Views: 187

Answers (1)

Gilles &#39;SO- stop being evil&#39;
Gilles &#39;SO- stop being evil&#39;

Reputation: 107809

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.

Upvotes: 1

Related Questions