Optimize program to test for divisibility of numbers 3.0
Table generator

Your table generator has a bug, which caused it to crash on my machine.  This line:


  if(*len &gt; buflen) {



should be:

  if(*len &gt;= buflen) {


Second, your table generator is outputting entries for permutations that aren't required.  For example, since 12 and 21 are permutations of each other, you only need to output "-12 21", and later on, there shouldn't be a "-21" entry because you've already checked for 21.  But currently, your table includes both, so your program will check entries that it doesn't need to check.

Incorrect table searching

There are a couple of things wrong with your program.  The biggest problem is that you are starting over at index 1 every time through the loop.  You really don't have to do that because to get to the next number, you just need to skip all the negative numbers.  In other words:


   for(x=1;x&lt;MAX;x++) {
     j=x-1;
     i=-x;



should be:

    j = 0;
    for(x=1;x&lt;MAX;x++) {
      i=-x;


Just making that change with your current table reduces the program time back down to "normal" levels, although it still isn't correct.

A second problem is that you are skipping lookup[j] when doing the dividing loop.  This is because your loop uses a preincrement, most likely because you are trying to avoid the first number of the sequence, which is negative.


  m = j;
  while((k = lookup[++m]) &gt; 0) {



What you can do is change the table's negative entry to positive.  Then you can use a postincrement:

lookup[j] = -lookup[j];
for(l=0;l&lt;N;l++) {
  m = j;
  while((k = lookup[m++]) &gt; 0) {
    if(k%n[l]==0)break;
  }
  if(k&lt;0) goto outer;
}


Searching the optimized table

Once you start using a table that doesn't include redundant entries, your search will need to change.  Your current search looks for the next number.  But since not every number will exist, all you need to do is search for a non-negative number.  Also, I appended a -1000000 entry at the end of my table to make sure I didn't run past the end of the table.

Your current search:   


 while((unsigned int)(j) &lt; LENGTH(lookup) &amp;&amp; lookup[j] != i) ++j;



would turn into:

while (lookup[j] &gt;= 0)
    ++j;


Putting it all together

This is what your code would look like with all the changes.  This code assumes that the table you generate has a -1000000 entry at the end and contains no redundant entries:

#include &lt;stdio.h&gt;

int lookup[] = {
#include "table.h"
};

#define MAX 1000000

int main(void) {
  int n[100];
  int i, j, k, m, N;

  scanf("%d", &amp;N);
  for(i=0;i&lt;N;i++) scanf("%d", &amp;n[i]);
  for(i=0;i&lt;MAX;i++) {
    while(lookup[i] &gt;= 0)
        ++i;
    lookup[i] = -lookup[i];
    for(j=0;j&lt;N;j++) {
      m = i;
      while((k = lookup[m++]) &gt; 0) {
        if(k%n[j]==0)break;
      }
      if(k&lt;0) goto outer;
    }
    break;
    outer:
    continue;
  }
  fprintf(stdout, "%d\n", lookup[i]);
}


You can find my own version of the table generator and solver program here on Github.