Printing the Largest Prime Factor of a Composite N

Question

I was solving a puzzle, where im required to find the largest Prime Factor of a composite number entered by the user. I thought of something and have tried it out, but it doesn't manage to detect the largest prime factor amongst the factors of the composite number.

I'm appending my code below, I'd be grateful if anyone could help me out here to get to detect the largest prime no. amongst the factors and print it.

// Accept a composite number from user and print its largest prime factor.

#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=2; j<=i/2; j++) //since a numbr cand be divisible by a number greated than its half
            {               if(i%j > 0) 
                    b = i;
                else if(i==3)
                    b = 3;
            }
        }
    }
    printf("%d\nLargest prime factor: %d\n", c, b);
}

Answer 1

The trick is, find the smallest prime factor, and divide the composite number c by it to obtain the largest prime factor.

The trick is to find the smallest factor F (starting from 2) where C / F is prime. Then, C / F will be the largest prime factor of C.

Edit: It looks like you also want to list all the factors. The problem is, in your inner loop that tests for primality, you set the largest prime to i for numbers that are divisible with anything. In other words, try something like this:

is_prime = true;

for (j = 2; j <= x / 2; j++) {
    if (i % j == 0)
        is_prime = false;
}

if (is_prime)
    largest_prime = x;

Note that you could actually stop sooner than x divided by 2. You could stop at the square root of x. However, the sqrt() function in <math.h> is a bit messy to work with in your case because it works with floating point numbers, not integers.

Answer 2

In Python, Something like this will do:

import math
import itertools

# largest prime factor of a composite number
def primality(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i ==0:
             return 0
    return 1

if __name__ == '__main__':
    number = 600851475143
    for i in itertools.count(2,1):
            if number%i == 0:
                if number%10 in [7,9,1,3] and primality(number/i):
                    print number/i
                    break

What I have done to check primality is the neat square root technique.

Answer 3

Factorization is a classic number theory problem. You can find many factorization algorithms in number theory textbooks. Some of them are available on wiki http://en.wikipedia.org/wiki/Integer_factorization

Answer 4

To find the prime factorization, you'd normally find all the factors between 2 and sqrt(N). You'd divide the composite by each of those to obtain the rest of the factors. Then recurse to find the prime factors of each of those.

When you're done, you'll have a list of all the prime factors. Getting the largest item in the list should be fairly trivial.

Answer 5

In your inner loop, you're setting b = i if there does exist a number that isn't a factor of i. You need to set b = i if there doesn't exist a number that is a factor of i.

(by "number", I mean "an integer between 2 and sqrt(i)" of course)

Answer 6

Hey thanks for the input friends, i worked out something and now the program prints the greatest prime factor of the composite number ,provided that the composite number is lesser than 52, while for higher ranges above this, it doesn't print the right output. I'm Appending the code, please see if you guys could help me around

#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++) //since a numbr cand be divisible by a number greated than its half
        {               if(i%j > 0)
                b = i; //b stores the largest prime factor
            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);

}