整数的素数分解

xaut3

素数定义：质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
; l& w- C" ]( r
素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！

#include <iostream>
using
2 q' |: n; B: d( z7 P, h! J' {& ~namespace std;

& y; k. `- O4 c% i# j7 Kvoid PrimaryCal(int num)
" K- }1 k; P6 Y6 C( F3 F; y{
2 O# O$ ~! Z/ D' c$ a/ J# C    for(int i=2;i*i<=num;i++)
# F4 A$ n- }4 H% v7 I    {
        while(num%i==0)
/ b' f, U! P# l& q1 i- ^+ _! F        {
# x4 v) ?8 V! W+ f, L# a* d            cout<<i<<"
9 |8 L' M0 b/ j+ S/ a";
+ S' q7 ?" j" V# ~; q! C; H$ R1 {            num/=i;
        }
    }
8 v' p  w3 \( ^' K2 t5 |    if(num!=1)
3 ]& Y8 J3 S  ?  B. {8 S/ e    {
1 N. }. h8 j! T) w        cout<<num;
: v( C+ s- E" G6 E    }
}

1 I" i# @9 u4 C2 X8 c8 \% U% }int main(void)
( S# w1 `/ V; j{
    for(int i=10;i<=100;i++)
    {
        cout<<i<<" = ";
        PrimaryCal(i);
$ n: w8 N( T- s, q& N        cout<<endl;
' _, A- ?+ N: C: Y6 h# o1 E# K    }
    return
-1;
}