整数的素数分解

xaut3

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

#include <iostream>
using
namespace std;
0 P" |6 P/ V& M7 {' P$ Z, w6 O
8 w' _$ M$ p+ H. o$ {$ B' c- b- N3 rvoid PrimaryCal(int num)
' ]1 i7 p- Q) v5 }5 f+ U$ E! ~; c. `{
0 f+ x' z& K3 F' G8 D: u    for(int i=2;i*i<=num;i++)
* O" b8 U% y+ T% ~2 ^- {0 h! b    {
! m, A/ j/ g7 d2 Y        while(num%i==0)
" ]$ Q0 V9 V- J' _6 c7 v! t        {
! P  d- ]* V4 |# z- V  {            cout<<i<<"
";
            num/=i;
        }
; `0 [- y5 e! d' D: W6 E    }
    if(num!=1)
    {
! v! U  S  J& o, H5 M        cout<<num;
    }
}

& [) O' Q: e6 I' S, s; C" ^9 @int main(void)
{
9 d8 l8 K- Q9 q% x9 z" n    for(int i=10;i<=100;i++)
    {
  F$ r% a$ k. d) m6 Z' `        cout<<i<<" = ";
+ n7 i; D0 B( [% ~& S        PrimaryCal(i);
        cout<<endl;
) k6 ~: y$ I/ A( q    }
    return
-1;
) k. t* y" R4 i+ Z; I}