---
description: The Prime factor of a given any number is the factor that is a prime number.
title: Prime Factor Algorithm: C, Python Example
image: https://www.guru99.com/images/prime-factor-algorithm.png
---

 

[Skip to content](#main) 

**⚡ Smart Summary**

Prime Factor Algorithm decomposes any positive integer into a product of prime numbers using trial division up to the square root, or a Sieve-of-Eratosthenes variant that stores each smallest prime factor.

* 🧮 **Definition:** Prime factors of an integer are the primes whose product equals it; 10 splits into 2 and 5.
* 🔁 **Trial Division:** Iterating from 2 up to sqrt(n) and dividing whenever the modulus is zero runs in O(sqrt(n)) time.
* 🧰 **Sieve Method:** Storing the smallest prime factor for every value up to a bound cuts factorization to about O(log n) per query.
* 🐍 **Python Code:** Iterative and recursive Python implementations print each prime factor of an entered number.
* 💻 **C Code:** Matching iterative and recursive C programs demonstrate the same logic using stdio and a precomputed array.
* 🔐 **Uses:** Prime factorization powers divisibility checks, fraction simplification, common denominators, and number-based cryptographic keys.

[ Read More ](javascript:void%280%29;) 

![Prime Factor Algorithm](https://www.guru99.com/images/prime-factor-algorithm.png)

## What is a Prime Factorization?

The prime factor of a number is a factor that is itself a **prime number**, divisible only by 1 and itself.

**Example:** prime factors of 10 are 2 and 5, since 2 × 5 = 10.

## Finding the Prime Factors using Iteration

Iterate from 2 up to sqrt(n) and check divisibility. While n is divisible by the current candidate, divide and print.

**Example:** every prime greater than 40 fits n2+n+41, so n = 0, 1, 2 yields 41, 43, 47.

### How to print a prime factor of a number?

* Iterate numbers from 2 up to sqrt(n).
* Check the modulus of n against each candidate; a zero remainder means the candidate is a prime factor.
* Collect every prime that divides n.
* The routine runs in O(sqrt(n)) time complexity.

**Algorithm:**

Set a counter i to 2
While i <= sqrt(n):
    While n % i == 0:
        n = n / i
        print i
    i = i + 1
if n > 1:
    print n

## Sieve Algorithm

The Sieve method stores the smallest prime factor of every number up to a maximum bound, sharply cutting factorization cost after precomputation.

* Record the smallest prime factor of every integer up to the max limit.
* Take that smallest prime and add it to the factor set.
* Divide the number by that prime and repeat until it reaches 1.
* Each query runs in about O(log n).

**Example:** a prime other than 2 and 3 fits the form 6n-1 or 6n+1\. For example, 5 = 6(1)-1 and 19 = 6(3)+1.

**Algorithm:** define an [array](https://www.guru99.com/array-data-structure.html) that stores the smallest prime factor of each number, using the index as the initial value for every element.

Set array[1] to 1
Set i to 2
While i*i <= max_number:
    If array[i] == i:
        Set j to i*i
        While j <= max_number:
            If array[j] == j:
                array[j] = i
            j = j + i
    i = i + 1
while the_number != 1:
    print array[the_number]
    the_number = the_number / array[the_number]

### Related Articles

* [Graph Data Structure and Algorithms](https://www.guru99.com/graphs-in-data-structures.html)
* [Travelling Salesman Problem](https://www.guru99.com/travelling-salesman-problem.html)
* [Bisection Method Algorithm](https://www.guru99.com/bisection-method.html)
* [Bucket Sort Algorithm](https://www.guru99.com/bucket-sort.html)

## Python Prime Factors Using Iteration

The following Python code finds prime factors using the iterative trial-division method:

import math
def PrimeFactors(n):
    for i in range(2, int(math.sqrt(n)) + 1, 1):
        while n % i == 0:  # find all the occurrences of a prime factor
            print((int)(i))
            n = n // i
    if n != 1:  # if the number was originally a prime
        print((int)(n))
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

**Output:**

Enter the number you want: 4
2
2

### RELATED ARTICLES

* [0/1 Knapsack Problem Fix using Dynamic Programming Example ](https://www.guru99.com/knapsack-problem-dynamic-programming.html "0/1 Knapsack Problem Fix using Dynamic Programming Example")
* [Types of Graphs in Data Structure with Examples ](https://www.guru99.com/types-of-graphs-in-data-structure.html "Types of Graphs in Data Structure with Examples")
* [Pascal’s Triangle Formula with Examples ](https://www.guru99.com/pascals-triangle-formula-examples.html "Pascal’s Triangle Formula with Examples")
* [Shell Sort Algorithm with Example ](https://www.guru99.com/shell-sort-algorithm.html "Shell Sort Algorithm with Example")

## Python Prime Factors Using Recursion

The [Python](https://www.guru99.com/python-tutorials.html) code below uses the sieve method to find the prime factors of a given number.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    for i in range(1, High):
        array[i] = i
    for i in range(2, math.ceil(math.sqrt(High))):
        if array[i] == i:
            for j in range(i * i, High, i):
                if array[j] == j:
                    array[j] = i

def PrimeFactors(n):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

Sieve()
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

**Output:**

Enter the number you want: 4
2
2

## C Prime Factors Program Using Iteration

The same iterative solution written in [C](https://www.guru99.com/c-programming-language.html): enter a number, then for each candidate from 2 up to sqrt(n), check divisibility and print every occurrence of a prime factor.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)  // find all the occurrences of a prime factor
        {
            printf("%d\n", i);
            n /= i;
        }
    }
    if (n != 1)  // if the number was originally a prime
    {
        printf("%d", n);
    }
    return 0;
}

**Output:**

Enter the number you want: 2
2

## C Prime Factors Program Using Recursion

[](https://www.guru99.com/images/3/prime-factor-1.png)

The recursive C version mirrors the Python one: build the array of smallest prime factors, then recurse dividing by that factor until n reaches 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    for (int i = 1; i < Max; i++)
        array[i] = i;
    for (int i = 2; i * i <= Max; i++)
    {
        if (array[i] == i)
        {
            for (int j = i * i; j < Max; j += i)
            {
                if (array[j] == j)
                    array[j] = i;
            }
        }
    }
}

void PrimeFactors(int n)
{
    if (n == 1)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

**Output:**

Enter the number you want: 2
2

### Some interesting facts about Prime numbers

* Any even number other than 2 can be written as the sum of two primes (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
* There are no consecutive primes other than 2 and 3, because 2 is the only even prime.
* Every prime except 2 and 3 fits the form 6n + 1 or 6n − 1, where n is a positive integer.
* The set of prime factors of a number is unique.
* The number 1 is neither prime nor composite.
* Prime factorization helps with divisibility, fraction simplification, and finding common denominators.
* Prime factorization also underpins number-based cryptographic codes.

## FAQs

🧮 What is prime factorization in simple terms?

Prime factorization breaks an integer into a product of primes, for example 12 = 2 × 2 × 3\. The prime factors are unique for every integer above one.

🔁 Why iterate only up to the square root of n?

If n has a factor greater than sqrt(n), its pair is smaller and would already be found. Anything past sqrt(n) repeats work.

⚙️ What is the time complexity of prime factorization?

Trial division runs in O(sqrt(n)). The sieve precomputes smallest prime factors in O(N log log N), then answers each factorization in about O(log n).

🧰 When should the sieve method be preferred?

Use the sieve when factorizing many numbers within a known upper bound. One precomputation lets each later query run in about O(log n).

🔢 Is 1 a prime factor of every number?

No. The number 1 is neither prime nor composite, so it never appears in a prime factor list. Prime factorization uses primes greater than or equal to 2.

🔐 How is prime factorization used in real applications?

Prime factorization drives divisibility tests, fraction simplification, LCM and GCD, and public-key cryptography like RSA, where factoring a large product of two primes is hard.

🤖 How does AI or machine learning use prime factorization?

AI systems apply prime factorization to number-theoretic features, cryptographic key analysis, and secure federated learning. Post-quantum ML research also studies factoring resistance.

🧠 Can AI Copilot tools automate writing a prime factorization program?

Yes. GitHub Copilot and similar AI assistants automate boilerplate for trial-division and sieve routines, though developers still verify complexity and edge cases such as n = 1.

#### Summarize this post with:

ChatGPT Perplexity Grok Google AI 

**Stay Updated on AI** **Get Weekly AI Skills, Trends, Actionable Advice.** 

##### Sign up for the newsletter

Subscribe for Free 

You have successfully subscribed.  
Please check your inbox. 

![AI-Newsletter]() Chosen by over **350,000+** professionals 

[Scroll to top ](#wrapper)Scroll to top 

× 

Toggle Menu Close 

Search for: 

Search

```json
{"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://www.guru99.com/#organization","name":"Guru99","sameAs":["https://www.facebook.com/Guru99Official","https://twitter.com/guru99com"],"logo":{"@type":"ImageObject","@id":"https://www.guru99.com/#logo","url":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","contentUrl":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","caption":"Guru99","inLanguage":"en-US"}},{"@type":"WebSite","@id":"https://www.guru99.com/#website","url":"https://www.guru99.com","name":"Guru99","publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US"},{"@type":"ImageObject","@id":"https://www.guru99.com/images/prime-factor-algorithm.png","url":"https://www.guru99.com/images/prime-factor-algorithm.png","width":"700","height":"250","caption":"Prime Factor Algorithm","inLanguage":"en-US"},{"@type":"BreadcrumbList","@id":"https://www.guru99.com/prime-factor.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":"1","item":{"@id":"https://www.guru99.com","name":"Home"}},{"@type":"ListItem","position":"2","item":{"@id":"https://www.guru99.com/design-algorithm","name":"Algorithm"}},{"@type":"ListItem","position":"3","item":{"@id":"https://www.guru99.com/prime-factor.html","name":"Prime Factor Algorithm: C, Python Example"}}]},{"@type":"WebPage","@id":"https://www.guru99.com/prime-factor.html#webpage","url":"https://www.guru99.com/prime-factor.html","name":"Prime Factor Algorithm: C, Python Example","dateModified":"2026-07-06T12:13:32+05:30","isPartOf":{"@id":"https://www.guru99.com/#website"},"primaryImageOfPage":{"@id":"https://www.guru99.com/images/prime-factor-algorithm.png"},"inLanguage":"en-US","breadcrumb":{"@id":"https://www.guru99.com/prime-factor.html#breadcrumb"}},{"@type":"Person","@id":"https://www.guru99.com/author/sarah","name":"Sarah Chen","description":"I'm Sarah Chen, a Senior Algorithm Engineer, dedicated to guiding you through the intricacies of algorithm engineering with clear, concise advice.","url":"https://www.guru99.com/author/sarah","image":{"@type":"ImageObject","@id":"https://www.guru99.com/images/sarah-chen-author.png","url":"https://www.guru99.com/images/sarah-chen-author.png","caption":"Sarah Chen","inLanguage":"en-US"},"worksFor":{"@id":"https://www.guru99.com/#organization"}},{"articleSection":"Algorithm","headline":"Prime Factor Algorithm: C, Python Example","description":"The Prime factor of a given any number is the factor that is a prime number.","keywords":"algorithm","speakable":{"@type":"SpeakableSpecification","cssSelector":[".entry-title",".summary"]},"@type":"Article","author":{"@id":"https://www.guru99.com/author/sarah","name":"Sarah Chen"},"dateModified":"2026-07-06T12:13:32+05:30","image":{"@id":"https://www.guru99.com/images/prime-factor-algorithm.png"},"copyrightYear":"2026","name":"Prime Factor Algorithm: C, Python Example","subjectOf":[{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is prime factorization in simple terms?","acceptedAnswer":{"@type":"Answer","text":"Prime factorization breaks a positive integer into a multiplication of prime numbers. For example, 12 = 2 x 2 x 3. The prime factors are unique for every integer greater than one."}},{"@type":"Question","name":"Why iterate only up to the square root of n?","acceptedAnswer":{"@type":"Answer","text":"If n has a factor larger than sqrt(n), the paired factor must be smaller than sqrt(n) and would be found first. Iterating past sqrt(n) is unnecessary and would repeat work already handled."}},{"@type":"Question","name":"What is the time complexity of prime factorization?","acceptedAnswer":{"@type":"Answer","text":"Trial division runs in O(sqrt(n)) per number. The sieve approach precomputes smallest prime factors in O(N log log N) and then answers each factorization query in about O(log n) time."}},{"@type":"Question","name":"When should the sieve method be preferred?","acceptedAnswer":{"@type":"Answer","text":"Use the sieve when factorizing many numbers within a known upper bound. Precomputing once and answering many queries in O(log n) is faster than repeated trial division on every input."}},{"@type":"Question","name":"Is 1 a prime factor of every number?","acceptedAnswer":{"@type":"Answer","text":"No. The number 1 is neither prime nor composite, so it is never listed among the prime factors. Prime factorization always uses primes greater than or equal to 2."}},{"@type":"Question","name":"How is prime factorization used in real applications?","acceptedAnswer":{"@type":"Answer","text":"Prime factorization drives divisibility tests, fraction simplification, LCM and GCD, and public-key cryptography such as RSA, where factoring a large product of two primes is computationally hard."}},{"@type":"Question","name":"How does AI or machine learning use prime factorization?","acceptedAnswer":{"@type":"Answer","text":"AI systems use prime factorization for number-theoretic feature engineering, cryptographic key analysis, and secure federated learning. Post-quantum machine learning research also studies factoring resistance for privacy-preserving model exchange."}},{"@type":"Question","name":"Can AI Copilot tools automate writing a prime factorization program?","acceptedAnswer":{"@type":"Answer","text":"Yes. AI Copilot assistants such as GitHub Copilot automate boilerplate for trial-division and sieve routines in Python and C, but developers still verify complexity, edge cases at n = 1, and integer overflow."}}]}],"@id":"https://www.guru99.com/prime-factor.html#schema-1132087","isPartOf":{"@id":"https://www.guru99.com/prime-factor.html#webpage"},"publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US","mainEntityOfPage":{"@id":"https://www.guru99.com/prime-factor.html#webpage"}}]}
```