Finding largest prime factor of a composite number in c

I am accepting a composite number as an input. I开发者_开发知识库 want to print all its factors and also the largest prime factor of that number. I have written the following code. It is working perfectly ok till the number 51. But if any number greater than 51 is inputted, wrong output is shown. how can I correct my code?

#include<stdio.h>
void main()
{
 int i, j, b=2, c;
 printf("\nEnter a composite number: ");
 scanf("%d", &c);
 printf("Factors: ");

 for(i=1; i<=c/2; i++)
 {
  if(c%i==0)
  {
   printf("%d ", i);
   for(j=1; j<=i; j++)
   {
    if(i%j > 0)
    {
     b = i;
    }
    if(b%3==0)
     b = 3;
    else if(b%2==0)
     b = 2;
    else if(b%5==0)
     b = 5;
   }
  }
 }
 printf("%d\nLargest prime factor: %d\n", c, b);
}

---

This is a bit of a spoiler, so if you want to solve this yourself, don't read this yet :). I'll try to provide hints in order of succession, so you can read each hint in order, and if you need more hints, move to the next hint, etc.

Hint #1: If divisor is a divisor of n, then n / divisor is also a divisor of n. For example, 100 / 2 = 50 with remainder 0, so 2 is a divisor of 100. But this also means that 50 is a divisor of 100.

Hint #2 Given Hint #1, what this means is that we can loop from i = 2 to i*i <= n when checking for prime factors. For example, if we are checking the number 100, then we only have to loop to 10 (10*10 is <= 100) because by using hint #1, we will get all the factors. That is:

100 / 2 = 50, so 2 and 50 are factors
100 / 5 = 20, so 5 and 20 are factors
100 / 10 = 10, so 10 is a factor

Hint #3 Since we only care about prime factors for n, it's sufficient to just find the first factor of n, call it divisor, and then we can recursively find the other factors for n / divisor. We can use a sieve approach and mark off the factors as we find them.

Hint #4 Sample solution in C:

bool factors[100000];

void getprimefactors(int n) {
  // 0 and 1 are not prime
  if (n == 0 || n == 1) return;

  // find smallest number >= 2 that is a divisor of n (it will be a prime number)
  int divisor = 0;
  for(int i = 2; i*i <= n; ++i) {
    if (n % i == 0) {
      divisor = i;
      break;
    }
  }
  if (divisor == 0) {
    // we didn't find a divisor, so n is prime
    factors[n] = true;
    return;
  }

  // we found a divisor
  factors[divisor] = true;
  getprimefactors(n / divisor);
}

int main() {
  memset(factors,false,sizeof factors);
  int f = 1234;
  getprimefactors(f);
  int largest;
  printf("prime factors for %d:\n",f);
  for(int i = 2; i <= f/2; ++i) {
    if (factors[i]) {
      printf("%d\n",i);
      largest = i;
    }
  }
  printf("largest prime factor is %d\n",largest);
  return 0;
}

Output:

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
prime factors for 1234:
2
617
largest prime factor is 617
> Terminated with exit code 0.

---

I presume you're doing this to learn, so I hope you don't mind a hint.

I'd start by stepping through your algorithm on a number that fails. Does this show you where the error is?

---

You need to recode so that your code finds all the prime numbers of a given number, instead of just calculating for the prime numbers 2,3, and 5. In other words, your code can only work with the number you are calculating is a prime number or is a multiple of 2, 3, or 5. But 7, 11, 13, 17, 19 are also prime numbers--so your code should simply work by finding all factors of a particular number and return the largest factor that is not further divisible.

---

Really, this is very slow for all but the smallest numbers (below, say, 100,000). Try finding just the prime factors of the number:

#include <cmath>

void addfactor(int n) {
    printf ("%d\n", n);
}

int main()
{
    int d;
    int s;
    int c = 1234567;
    while (!(c&1)) {
        addfactor(2);
        c >>= 1;
    }
    while (c%3 == 0) {
        addfactor(3);
        c /= 3;
    }
    s = (int)sqrt(c + 0.5);
    for (d = 5; d <= s;) {
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 2;
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 4;
    }
    if (c > 1)
        addfactor(c);
    return 0;
}

where addfactor is some kind of macro that adds the factor to a list of prime factors. Once you have these, you can construct a list of all the factors of the number.

This is dramatically faster than the other code snippets posted here. For a random input like 10597959011, my code would take something like 2000 bit operations plus 1000 more to re-constitute the divisors, while the others would take billions of operations. It's the difference between 'instant' and a minute in that case.

---

Simplification to dcp's answer(in an iterative way):

#include <stdio.h>
void factorize_and_print(unsigned long number) {
  unsigned long factor;
  for(factor = 2; number > 1; factor++) {
    while(number % factor == 0) {
      number = number / factor;
      printf("%lu\n",factor);
    }
  }
}

/* example main */
int main(int argc,char** argv) {
  if(argc >= 2) {
    long number = atol(argv[1]);
    factorize_and_print(number);
  } else {
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]);
  }
}

Note: There is a number parsing bug here that is not getting the number in argv correctly.