整数的素数分解

xaut3

素数定义：质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
9 q6 s2 g* h7 @( v! g
' k+ Z% k1 B; A' Q$ b素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！

#include <iostream>
using
# Z6 u8 s! ?2 Y& \8 r! B( }namespace std;
) Q: ?1 k0 @( E# M/ n/ f6 ?
void PrimaryCal(int num)
' U( g6 @$ ^6 J" e7 H{
& i  z" X( \. W' X) |    for(int i=2;i*i<=num;i++)
8 T- q$ G8 O' K5 m, r3 a- Q- i, Z+ G    {
: Z, W- I, Q/ }5 M2 s        while(num%i==0)
        {
            cout<<i<<"
- d; G5 S* n+ S! _$ s; p2 f";
            num/=i;
        }
, ]: R$ s0 R1 p0 Q6 n- Q    }
. K! h! T+ N4 w) L9 q    if(num!=1)
    {
  r8 v: |; ^7 Z4 D7 m' m* Q        cout<<num;
    }
; N9 v4 s0 T; n7 N. _; H$ t}

3 u6 C  g, K% T# @( \. Cint main(void)
3 u+ Q& {* D; m5 R) l{
    for(int i=10;i<=100;i++)
* a+ V3 w. _' X    {
, o8 S% ~' W0 T5 M# F( O8 g5 v        cout<<i<<" = ";
        PrimaryCal(i);
) p# j1 |- S# f2 A1 O        cout<<endl;
    }
- Y8 l4 V; C% R, o3 G    return
  \0 k2 e. V0 X! B7 K, F( z7 C1 P-1;
8 E$ D  a& u4 X: F}