整数的素数分解

xaut3

素数定义：质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。

) w( T0 Z' [- `& s/ ^& b素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！

#include <iostream>
5 @+ _. C) Z3 v5 q5 Iusing
# i( O( U+ ~5 b+ _7 ~namespace std;

( P; ~- a% T% m5 S& b# Zvoid PrimaryCal(int num)
{
    for(int i=2;i*i<=num;i++)
3 F% _6 x3 a0 w    {
0 g( }+ ^8 [  r4 w) @        while(num%i==0)
        {
            cout<<i<<"
";
. L) N7 a# S5 u8 S# a            num/=i;
+ c- o) R6 W" c+ ?/ J        }
    }
5 |# Z1 I! O/ P/ \0 Z" u    if(num!=1)
. U! p4 V: w7 r) Q    {
0 R  ]6 T' h3 G  p, X# R" f9 C        cout<<num;
    }
( g- A0 ]( R( c8 ~}

: P' \0 _8 E" Y  D% Oint main(void)
{
; l* `# ?. _/ @% z    for(int i=10;i<=100;i++)
; Y+ E! N; T* O$ H. Z    {
        cout<<i<<" = ";
7 f- N1 p2 b8 @4 b7 `% \        PrimaryCal(i);
3 G' }' H9 n; u4 W$ J- k        cout<<endl;
1 @: s1 e% P2 P+ C8 k( |    }
4 n) L1 n$ e8 K( J    return
' v+ }9 s/ h+ n- F5 w-1;
' c! \/ o: j( V. c}