整数的素数分解

xaut3

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

素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！

$ w2 u, r5 g: c8 n/ a#include <iostream>
8 F9 |  ?+ c7 ?6 Q- Z5 Dusing
namespace std;

3 n! Q, z/ h% ?- X" r) ovoid PrimaryCal(int num)
8 O, S5 l0 l) u: D" [+ H9 ~{
    for(int i=2;i*i<=num;i++)
* z- I8 j1 ^5 C0 O    {
        while(num%i==0)
  ]- o# e: b" F0 W- H        {
            cout<<i<<"
9 r0 t3 D4 \9 B9 x% g% M";
            num/=i;
- M: z: ~4 m" t2 {; [' V        }
    }
    if(num!=1)
( Y1 K4 I, g$ c; S2 \& i4 }    {
& U3 K* r1 u0 H- h        cout<<num;
1 Z) W0 ?. n/ p* T    }
}

4 ~/ y7 r9 V( y. G& ]% f) e# B* fint main(void)
{
2 E# s8 t9 ~- `5 N; N  x5 Z    for(int i=10;i<=100;i++)
- k0 e5 ?) T- e+ I# D    {
# W4 N7 Q$ L6 m" {: G        cout<<i<<" = ";
) b/ O$ i$ K) |$ G4 z/ p+ {        PrimaryCal(i);
% v) X$ Y4 |' Y9 s        cout<<endl;
$ C; @: [. s# |* w1 E: P! q1 I/ ]$ `    }
* `# y; V% a4 e/ i4 \$ A/ L7 p; C    return
-1;
- n) W0 J3 m1 ~8 Q( d; v}