2

This function below checks to see if an integer is prime or not.

I'm running a for loop from 3 to 2147483647 (+ve limit of long int).

But this code hangs, can't find out why?

#include<time.h>
#include<stdio.h>
int isPrime1(long t)
{
    long i;
    if(t==1) return 0;
    if(t%2==0) return 0;
    for(i=3;i<t/2;i+=2)
    {
        if(t%i==0) return 0;
    }
    return 1;
}
int main()
{
    long i=0;
    time_t s,e;

    s = time(NULL);
    for(i=3; i<2147483647; i++)
    {
        isPrime1(i);
    }
    e = time(NULL);
    printf("\n\t Time : %ld secs", e - s );
    return 0;
}
6
  • 2
    Are you sure it really hangs and it's not that it just takes a very long time to execute?
    – FatalError
    Apr 21, 2013 at 16:32
  • 1
    Are you sure it is actually stuck in a loop and not just REALLY long to execute?
    – Thibaut
    Apr 21, 2013 at 16:32
  • I don't think it's an infinite loop. You simply have more than 2147483647 loop, that's all. Way too heavy Apr 21, 2013 at 16:32
  • Maybe thats just to much for your computer, have you tried with a less bigger number like for(i=3; i<100; i++) ?
    – Melki
    Apr 21, 2013 at 16:33
  • 2
    the complexity of this thing looks n^2 to me, so 2147483647 might be pushing it.
    – Thibaut
    Apr 21, 2013 at 16:33

4 Answers 4

5

It will eventually terminate, but will take a while, if you look at your loops when you inline your isPrime1 function, you have something like:

for(i=3; i<2147483647; i++)
   for(j=3;j<i/2;j+=2)

which is roughly n*n/4 = O(n^2). Your loop trip count is way too high.

2

It depends upon the system and the compiler. On Linux, with GCC 4.7.2 and compiling with gcc -O2 vishaid.c -o vishaid the program returns immediately, and the compiler is optimizing all the call to isPrime1 by removing them (I checked the generated assembler code with gcc -O2 -S -fverbose-asm, then main does not even call isPrime1). And GCC is right: since isPrime1 has no side-effect and its result is not used, its call can be removed. Then the for loop has an empty body, so can also be optimized.

The lesson to learn is that when benchmarking optimized binaries, you better have some real side-effect in your code.

Also, arithmetic tells us that some i is prime if it has no divisors less than its square root. So better code:

int isPrime1(long t) {
  long i;
  double r = sqrt((double)t);
  long m = (long)r;
  if(t==1) return 0;
  if(t%2==0) return 0;
  for(i=3;i <= m;i +=2)
    if(t%i==0) return 0;
  return 1; 
}

On my system (x86-64/Debian/Sid with i7 3770K Intel processor, the core running that program is at 3.5GHz) long-s are 64 bits. So I coded

int main ()
{
  long i = 0;
  long cnt = 0;
  time_t s, e;

  s = time (NULL);
  for (i = 3; i < 2147483647; i++)
    {
      if (isPrime1 (i) && (++cnt % 4096) == 0) {
        printf ("#%ld: %ld\n", cnt, i);
        fflush (NULL);
      }
    }
  e = time (NULL);
  printf ("\n\t Time : %ld secs\n", e - s);
  return 0;
}   

and after about 4 minutes it was still printing a lot of lines, including

#6819840: 119566439
#6823936: 119642749
#6828032: 119719177
#6832128: 119795597

I'm guessing it would need several hours to complete. After 30 minutes it is still spitting (slowly)

#25698304: 486778811
#25702400: 486862511
#25706496: 486944147
#25710592: 487026971

Actually, the program needed 4 hours and 16 minutes to complete. Last outputs are

#105086976: 2147139749
#105091072: 2147227463
#105095168: 2147315671
#105099264: 2147402489

   Time : 15387 secs

BTW, this program is still really inefficient: The primes program /usr/games/primes from bsdgames package is answering much quicker

% time /usr/games/primes 1 2147483647 | tail
2147483423
2147483477
2147483489
2147483497
2147483543
2147483549
2147483563
2147483579
2147483587
2147483629
/usr/games/primes 1 2147483647 
     10.96s user 0.26s system 99% cpu 11.257 total

and it has still printed 105097564 lines (most being skipped by tail)

If you are interested in prime number generation, read several math books (it is still a research subject if you are interested in efficiency; you still can get your PhD on that subject.). Start with the sieve of erasthothenes and primality test pages on Wikipedia.

Most importantly, compile first your program with debugging information and all warnings (i.e. gcc -Wall -g on Linux) and learn to use your debugger (i.e. gdb on Linux). You could then interrupt your debugged program (with Ctrl-C under gdb, then let it continue with the cont command to gdb) after about a minute and two, then observe that the i counter in main is increasing slowly. Perhaps also ask for profiling information (with -pg option to gcc then use gprof). And when coding complex arithmetic things it is well worth to read good math books about them (and primality test is a very complex subject, central to most cryptographic algorithms).

2
  • 2
    This is only happening because he is not doing anything with the return value in this case, since it is a minimal example. For a real program he is probably interested in the return value ;)
    – Thibaut
    Apr 21, 2013 at 16:38
  • I know that, but I wanted to attract the original poster to some interesting point about optimization and benchmarking. Apr 21, 2013 at 17:18
1

This is a very inefficient approach to test for primes, and that's why it seems to hang. Search the web for more efficient algorithms, such as the Sieve of Eratosthenes

0

Here try this, see if it's really an infinite loop

int main()
{
    long i=0;
    time_t s,e;

    s = time(NULL);
    for(i=3; i<2147483647; i++)
    {
        isPrime1(i);

        //calculate the time execution for each loop
        e = time(NULL);
        printf("\n\t Time for loop %d: %ld secs", i, e - s );
    }

    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.