Faster Prime factorization

Question

Now this is a very elementary question still I want to ask it. I want to know how can I find d the prime factorization of a number (<=10^12) quickly. Please help me. Please don't just post the code please explain too I am just a novice (that to don't know)

Answer 1

Example 2: What is the prime factorization of 147 ?

Can we divide 147 evenly by 2?

147 ÷ 2 = 73½

No it can't. The answer should be a whole number, and 73½ is not.

Let's try the next prime number, 3:

147 ÷ 3 = 49

That worked, now we try factoring 49, and find that 7 is the smallest prime number that works:

49 ÷ 7 = 7

And that is as far as we need to go, because all the factors are prime numbers.

147 = 3 × 7 × 7

(or 147 = 3 × 72 using exponents)

code

 #include<stdio.h>

 int main(){

 int num,i=1,j,k;

 printf("\nEnter a number:");

 scanf("%d",&num);

 while(i<=num){

  k=0;

  if(num%i==0){

     j=1;

      while(j<=i){

        if(i%j==0)

             k++;

         j++;

      }

      if(k==2)

         printf("\n%d is a prime factor",i);
  }

  i++;

  }

 return 0;

}

Answer 2

For numbers that small a simple factorization by trial division is sufficient:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            n := n / f
            append f to fs
        f := f + 1
    if n == 1 return fs
    append n to fs
    return fs

You'll need more powerful algorithms as the number being factored gets larger.

Answer 3

Very simple program for this,

    a=int (input("enter number"))

    i=2
    h=1
    c=a

while(h!=a):
 if(c%i==0):
  print(i)
  h=h*i
  c=c/i
 else:
  i=i+1