Day 20/100 Factor

Day 20/100 Factor

Primes and Factors

It's been 20 days so far, and I'm at a point where my momentum has been disrupted. This is because I'm at research stage where things are unknown. This week will probably feature the slowest progress as I am reorganizing my codes. Specifically, I'm doing this to create programs to use. I think that's the difference between my effort and other people's. They learn to code, I'm writing programs to use.

It's possible that I will take a week off next week as I am re-orienting myself. I still code everyday, just that I won't be showing off the programs I've written as they are too messy and raw.

Take today's program: It's Factor. There's actually a built-in program to do this. Have you seen the source code? It's rather messy! I'm certainly no mathematician. So, I did it the simple way. Even though I'm doing it the simplest way, it does the job quite fast most of the time. The internal program runs at 0.005s, while mine is at 0.027s. That's about 5 times difference, and that's quite normal. In other words, to achieve single digit multiple of performance, there's quite a bit you must do! That's fine by my book. Also remember that I'm not using Gnu C Compiler (GCC). I'm using Tiny C Compiler (TCC) because it compiles so fast.

Given all the disadvantages, I'm happy that the program performs at the speed that it is. Of course, if I'm factoring numbers greater than 32 bit, it can bog down quite a bit. Some of the larger numbers, such as those of 64 bit, may even take hours to do. However, the algorithm I use is very simple:

  printf("F1 %lld: ",n);
  for (i=1;i<=n;i++) {
    while ((n%i)==0) {
      printf("%lld ",i);
      n/=i; c++;
      if (i==1) i++;
    }
  }
  printf("\n");
  if (c==2) return 1;
  return 0;

  printf("F2 %lld: 1 ",n);
  for (i=n/2;n>1 && i>1;i--,c++) {
    if ((n%i)==0) {
      printf("%lld ",(n/i));
      n=i;
    }
  }
  printf("%lld\n",n);
  return (n/i);

As you can see, there are 2 versions of code. Both returns a condition if the number is prime, so you can check the number for prime. Like so:

    if (factor1(n)) puts("Prime");
    if (n==factor2(n)) puts("Prime");

And that makes all the difference. Trying to give that is what makes the code so challenging to write, especially since I'm approaching the problem from both direction: Increasing and Decreasing.

Most people, when given a problem, will solve it one way, but never bothered to solve it again another way. That's no way to learn! Always do it more than once. In fact, I habitually do it at least 3 times: The good way, the better way, and the best way. Adopting that philosophy yields the most efficient result in regard to cost/performance gain, and so I would encourage you to do it that way, too.

At the very least, try to approach the problem from opposite point of view. If you look left, look right! If you look up, look down! If you look forward, look backward! It's that easy! There's nothing stopping you from doing it, except yourself. 

The LeetCode challenge 254 expects you to output combinations as well, but when's the last time that kind of algorithm was used? Nothing that I can think of. Anyway, here is the completed factor program:

 
#include <stdio.h>
#include <stdlib.h>

int factor1(long long n) {
  long long i;
  long long c=0;

  printf("F1 %lld: ",n);

  for (i=1;i<=n;i++) {

    while ((n%i)==0) {

      printf("%lld ",i);

      n/=i; c++;

      if (i==1) i++;

    }

  }

  printf("\n");

  if (c==2) return 1;

  return 0;

}

int factor2(long long n) {
  long long i; long long c=0;
  printf("F2 %lld: 1 ",n);
  for (i=n/2;n>1 && i>1;i--,c++) {
    if ((n%i)==0) {
      printf("%lld ",(n/i));
      n=i;
    }
  }
  printf("%lld\n",n);
  return (n/i);
}

int main (int argc, char *argv[]) {
  int i,n;
  if (argc<2) { puts("factor [NUMBER] ..."); return 0; }

  for (i=1;i<argc;i++) {
    n=atoll(argv[i]);
    if (factor1(n)) puts("Prime");
    if (n==factor2(n)) puts("Prime");
  }
  return 0;
}

One more thing: In this case, I did another try another factoring algorithm involving recursion, but that didn't pan out, it being a fragile algorithm, so I didn't bother to show you. But it does take a few hours of my time as I try the algorithm, just so you know.