整数的素数分解

xaut3

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

! R% E9 ?9 @1 Q  B, [0 L素数是算法中经常提到的一种数的类型，求一个正整数的所有素数因子也是很多算法中经常用到的，今天在做一道算法题时也遇到了素数的求解，故在此记录一下，以备后用！
! B5 K$ Q9 e- u3 X* b4 r
#include <iostream>
using
namespace std;
. J3 y1 [+ X5 G1 b* R/ ^# k: }' k
void PrimaryCal(int num)
# Q7 u) d- Z9 G/ M{
* }+ F4 l: v9 D. T/ _" w    for(int i=2;i*i<=num;i++)
0 Q. U- H' A: e7 l    {
        while(num%i==0)
+ H; k1 z3 o4 Y/ c) i        {
4 p9 p, c5 u6 G) q: z# q4 C            cout<<i<<"
";
            num/=i;
        }
0 B+ s( b' u3 e, L9 `& Z/ D    }
    if(num!=1)
9 h' I+ o1 v, \    {
        cout<<num;
6 R, J7 u- H$ x1 |; W2 \; k    }
1 D0 Q; h  s, k* C}

  H% j" i6 ~& x" ~int main(void)
9 V3 t( Q* E: ]8 u5 Y/ C' s7 Y{
    for(int i=10;i<=100;i++)
$ ^4 Z% U! K6 z& V, @    {
        cout<<i<<" = ";
        PrimaryCal(i);
) v0 b" X, n! r1 s" b        cout<<endl;
! ]( ^8 ~0 [- y. m    }
  c, p  F7 u' A9 q    return
-1;
1 v2 B! n4 I: O. b1 e}