Prime factors of given number

Write a program to find the prime factors of a given number. 

Example 1:

Input : num = 24
Output: 2 2 2 3

Example 2:

Input: num = 13
Output: 13

Approach 1: Simple

C

#include <stdio.h>
int main()
{
    int num = 24;
    for (int i = 2; i * i <= num; i++)
    {
        while (num % i == 0)
        {
            printf("%d ", i);
            num = num / i;
        }
    }
    if (num > 1)
    {
        printf("%d ", num);
    }
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
public class PrimeFactor {
    public static void main(String[] args) {
        int num = 120;
        List<Integer> factor = calculateFactor(num);
        System.out.println("Factor is " + factor);
    }

    private static List<Integer> calculateFactor(int num) {
        List<Integer> factor = new ArrayList<>();
        for (int i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                factor.add(i);
                num = num / i;
            }
        }
        if (num > 1)
            factor.add(num);
        return factor;
    }
    //Time complexity: O(sqrt(n))
}

C++

#include <bits/stdc++.h>
using namespace std;
//function to find prime factors
//of given number
vector<int> primeFactor(int num)
{
    vector<int> prime;
    for(int i=2;i*i<=num;i++)
     {
         while(num%i==0)
            {
                prime.push_back(i);
                num=num/i;
            }
     }
     if(num>1)
       prime.push_back(num);
    return prime;
}
int main()
{
  int num=24;
  vector<int> prime=primeFactor(num);
  for(int i=0;i<prime.size();i++)
     cout<<prime[i]<<" ";
  return 0;
}
//Time complexity: O(sqrt(n))

Approach 2: After checking for 2. In this, we check only odd numbers.

C

#include <stdio.h>
int main()
{
    int num = 24;
    //if number is divisible by 2
    while (num % 2 == 0)
    {
        printf("%d ", 2);
        num = num / 2;
    }
    //now iterate from i=3 and skip all
    //even number
    for (int i = 3; i * i <= num; i += 2)
    {
        while (num % i == 0)
        {
            printf("%d ", i);
            num = num / i;
        }
    }
    if (num > 1)
    {
        printf("%d ", num);
    }
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
public class PrimeFactor {
    public static void main(String[] args) {
        int num = 120;
        List<Integer> factor = calculateFactor(num);
        System.out.println("Factor is " + factor);
    }

    private static List<Integer> calculateFactor(int num) {
        List<Integer> factor = new ArrayList<>();
        // if number is divisible by 2
        while (num % 2 == 0) {
            factor.add(2);
            num /= 2;
        }
        // skip all even number
        for (int i = 3; i * i <= num; i+=3) {
            while (num % i == 0) {
                factor.add(i);
                num = num / i;
            }
        }
        if (num > 1)
            factor.add(num);
        return factor;
    }
}
//Time Complexity: O(sqrt(n))
//Space Complexity:O(1)

C++

#include <bits/stdc++.h>
using namespace std;
//function to find the prime
//factor of the given number
vector<int> primeFactor(int num)
{
    vector<int> prime;
    //if numner is divisible by 2
    while(num%2==0)
      {
          prime.push_back(2);
          num=num/2;
      }
    //now iterate from i=3 and skip all
    //even number
    for(int i=3;i*i<=num;i+=2)
      {
          while(num%i==0)
            {
                prime.push_back(i);
                num=num/i;
            }
      }
    if(num>1)
       prime.push_back(num);
    return prime;
}
int main()
{
    int num=24;
    vector<int> prime=primeFactor(num);
    cout<<"Prime factors are\n";
    for(int i=0;i<prime.size();i++)
       cout<<prime[i]<<" ";
    return 0;
}
//Time Complexity: O(sqrt(n))
//Space Complexity:O(1)