质因子分解（求一个数的质数因子） _数字是否为质数

本文概述

C/C++
Java
python
C#
PHP

质数因子是指给定的质数的因数。因式就是把数相乘得到另一个数。简单地说，质数因子就是找出哪些质数相乘得到原来的数。
例子：
例:15的质数因子是3和5(因为3×5=15, 3和5是质数)。

文章图片
关于质数因子的一些有趣的事实：

对于任何数量, 只有一组(唯一！)素数因子。
为了保持唯一素数分解的这一特性, 必须将数字1既不是素数也不是复合数。
素因式分解可以帮助我们进行除数运算, 简化分数并找到分数的公共分母。
Pollard的Rho是素数分解算法, 对于大型复合数与小的主要因素。
密码学是对密码的研究。素数分解对于尝试根据数字创建(或破解)秘密代码的人们非常重要。

如何打印一个数的质数因子？
天真的解决方案：
给定一个数字n, 编写一个函数打印n的所有素数。例如, 如果输入数字为12,
那么输出应该是" 2 2 3", 如果输入数字是315, 那么输出应该是" 3 3 5 7"。
以下是查找所有主要因素的步骤：

当n被2整除时，打印2并将n除以2。。
步骤1之后，n必须为奇数。现在开始一个循环，从i = 3到n的平方根。当i除以n时，打印i并将n除以i，将i增加2，然后继续。
如果n是一个质数并且大于2，那么n在以上两步之后不会变成1。如果n大于2，输出n。

C/C++

// Program to print all prime factors # include < stdio.h> # include < math.h> // A function to print all prime factors of a given number n void primeFactors( int n) { // Print the number of 2s that divide n while (n%2 == 0) { printf ( "%d " , 2); n = n/2; }// n must be odd at this point.So we can skip // one element (Note i = i +2) for ( int i = 3; i < = sqrt (n); i = i+2) { // While i divides n, print i and divide n while (n%i == 0) { printf ( "%d " , i); n = n/i; } }// This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) printf ( "%d " , n); }/* Driver program to test above function */ int main() { int n = 315; primeFactors(n); return 0; }

Java

// Program to print all prime factors import java.io.*; import java.lang.Math; class GFG { // A function to print all prime factors // of a given number n public static void primeFactors( int n) { // Print the number of 2s that divide n while (n % 2 == 0 ) { System.out.print( 2 + " " ); n /= 2 ; }// n must be odd at this point.So we can // skip one element (Note i = i +2) for ( int i = 3 ; i < = Math.sqrt(n); i += 2 ) { // While i divides n, print i and divide n while (n % i == 0 ) { System.out.print(i + " " ); n /= i; } }// This condition is to handle the case whien // n is a prime number greater than 2 if (n > 2 ) System.out.print(n); }public static void main(String[] args) { int n = 315 ; primeFactors(n); } }

python

# Python program to print prime factorsimport math# A function to print all prime factors of # a given number n def primeFactors(n):# Print the number of two's that divide n while n % 2 = = 0 : print 2 , n = n / 2# n must be odd at this point # so a skip of 2 ( i = i + 2) can be used for i in range ( 3 , int (math.sqrt(n)) + 1 , 2 ):# while i divides n, print i ad divide n while n % i = = 0 : print i, n = n / i# Condition if n is a prime # number greater than 2 if n > 2 : print n# Driver Program to test above functionn = 315 primeFactors(n)# This code is contributed by Harshit Agrawal

// C# Program to print all prime factors using System; namespace prime { public class GFG {// A function to print all prime // factors of a given number n public static void primeFactors( int n) { // Print the number of 2s that divide n while (n % 2 == 0) { Console.Write(2 + " " ); n /= 2; }// n must be odd at this point. So we can // skip one element (Note i = i +2) for ( int i = 3; i < = Math.Sqrt(n); i += 2) { // While i divides n, print i and divide n while (n % i == 0) { Console.Write(i + " " ); n /= i; } }// This condition is to handle the case whien // n is a prime number greater than 2 if (n > 2) Console.Write(n); }// Driver Code public static void Main() { int n = 315; primeFactors(n); } } }// This code is contributed by Sam007

PHP

< ?php // PHP Efficient program to print all // prime factors of a given number// function to print all prime // factors of a given number n function primeFactors( $n ) {// Print the number of // 2s that divide n while ( $n % 2 == 0) { echo 2, " " ; $n = $n / 2; }// n must be odd at this // point. So we can skip // one element (Note i = i +2) for ( $i = 3; $i < = sqrt( $n ); $i = $i + 2) {// While i divides n, // print i and divide n while ( $n % $i == 0) { echo $i , " " ; $n = $n / $i ; } }// This condition is to // handle the case when n // is a prime number greater // than 2 if ( $n > 2) echo $n , " " ; }// Driver Code $n = 315; primeFactors( $n ); // This code is contributed by aj_36 ?>

输出如下：