整数的素数分解

xaut3

素数定义：质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
( P! N$ l* h8 D8 y  b  d7 S
/ w$ Z/ m( b- G1 w7 A* S9 E% A) |素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！
' M0 m* E; O0 ~# I. t1 G
#include <iostream>
; x$ \3 j9 Y# W+ S+ D- S# Xusing
namespace std;
% c' u5 r. ]  H6 H# h5 A! Q5 X% f5 k
9 x# |& m$ w; {+ Q0 \void PrimaryCal(int num)
' v6 `8 K+ P2 n, X1 Q( K" q{
    for(int i=2;i*i<=num;i++)
    {
, x0 C* t8 n5 n# I+ W        while(num%i==0)
# U* d0 ~2 y: `1 \- w        {
, `, `! G- w/ v0 s4 m, a$ w. W            cout<<i<<"
2 }! _1 b" j8 |# U4 a$ ~5 w, l";
            num/=i;
6 G% z8 j( o3 M4 K  J  p- B        }
8 z' x* Y" L! @* x    }
    if(num!=1)
7 ^; c% h1 y7 k* }1 A    {
- ~, B+ R  }% u) y' \) ]. M5 c        cout<<num;
2 s$ K' P! h3 J    }
}
; T' ?) a( D8 u( T) D: O* J
int main(void)
{
) `2 b# o4 V1 W; a2 q2 J    for(int i=10;i<=100;i++)
    {
/ t% n, J% \6 N& }/ r- S: y$ Q4 _, s        cout<<i<<" = ";
, o& H7 \# y- E0 P( i        PrimaryCal(i);
        cout<<endl;
    }
    return
-1;
8 R- ~# |+ S+ _0 ]" |! g' E$ I  j}