Finding largest prime factor of a composite number in c

Question

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

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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.