素数因子算法：C， Python 例如：

由： 陈莎拉 陈莎拉
Hours 更新

⚡ 智能摘要

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.

  • 🧮 定义： 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.
  • 🔐 用途： Prime factorization powers divisibility checks, fraction simplification, common denominators, and number-based cryptographic keys.
阅读更多

素因数算法

什么是质因数分解？

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

计费示例： prime factors of 10 are 2 and 5, since 2 × 5 = 10.

使用迭代查找质因数

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

计费示例： every prime greater than 40 fits n2+n+41, so n = 0, 1, 2 yields 41, 43, 47.

如何打印一个数字的质因数？

  • 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.

算法：

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

筛选算法

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).

计费示例： 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.

算法： define an 排列 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]

相关文章

Python 使用迭代法求质因数

下列 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)

输出：

Enter the number you want: 4
2
2

相关文章

Python 使用递归计算质因数

此 Python 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)

输出：

Enter the number you want: 4
2
2

使用迭代的 C 素数因子程序

The same iterative solution written in C: 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;
}

输出：

Enter the number you want: 2
2

使用递归的 C 素数因数程序

使用递归的 C 素数因数程序

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

输出：

Enter the number you want: 2
2

关于质数的一些有趣事实

  • 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.

常见问题

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.

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

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).

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

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.

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.

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

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.

总结一下这篇文章：