求一个数的最大素因子(python实现)

　　首先想到的是，将这个数进行素因子分解，得到所有的因子，然后取最大的。

　　首先写一个判断一个数是否是素数的方法：

　　

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

<code>#judge a number whether a prime</code>

<code>    </code><code>def</code>

<code>judgeprime(</code><code>self</code><code>,number,pme):</code>

<code>        </code><code>if</code>

<code>number &lt;</code><code>2</code><code>:</code>

<code>            </code><code>return</code>

<code>false</code><code>;</code>

<code>number</code><code>=</code><code>=</code>

<code>2</code><code>:</code>

<code>true</code><code>;</code>

<code>        </code><code>for</code>

<code>p</code><code>in</code>

<code>pme:</code>

<code>            </code><code>if</code>

<code>p</code><code>=</code><code>=</code>

<code>                </code><code>continue</code><code>;</code>

<code>            </code><code>q</code><code>=</code>

<code>number</code><code>/</code><code>p;</code>

<code>            </code><code>r</code><code>=</code>

<code>number</code><code>%</code><code>p;</code>

<code>r</code><code>=</code><code>=</code>

<code>0</code><code>:</code>

<code>                </code><code>return</code>

<code>            </code><code>else</code><code>:</code>

<code>                </code><code>if</code>

<code>q &lt; p:</code>

<code>                    </code><code>return</code>

<code>                </code><code>else</code><code>:</code>

<code>                    </code><code>continue</code><code>;</code>

　　然后求出所有比这个数的平方根小的素数：

<code>#get all prime under a number,include this number</code>

<code>getprimeundernumber(</code><code>self</code><code>,number):</code>

<code>        </code><code>pme</code><code>=</code>

<code>[];</code><code>#definite a prime list</code>

<code>        </code><code>pme.append(</code><code>2</code><code>);</code>

<code>        </code><code>pme.append(</code><code>3</code><code>);</code>

<code>number &lt;</code><code>5</code><code>:</code>

<code>            </code><code>print</code>

<code>‘please input a number above 5‘</code><code>;</code>

<code>            </code><code>return</code><code>;</code>

<code>        </code><code>i</code><code>=</code>

<code>5</code><code>;</code>

<code>        </code><code>while</code>

<code>i &lt;</code><code>=</code>

<code>number:</code>

<code>            </code><code>flag</code><code>=</code>

<code>self</code><code>.judgeprime(i,pme);</code>

<code>flag:</code>

<code>                </code><code>pme.append(i);</code>

<code>                </code><code>i</code><code>=</code>

<code>i</code><code>+</code> <code>2</code><code>;</code>

<code>        </code><code>return</code>

<code>pme;</code>

　　分解素因子

23

24

25

<code># decomposition factors</code>

<code>getdecompositionfactors(</code><code>self</code><code>,number):</code>

<code>math.sqrt(number) &lt;</code><code>5</code><code>:</code>

<code>            </code><code>primelist</code><code>=</code>

<code>self</code><code>.getprimeundernumber(</code><code>5</code><code>);</code>

<code>        </code><code>else</code><code>:</code>

<code>self</code><code>.getprimeundernumber(math.sqrt(number));</code>

<code>2</code> <code>or</code>

<code>3</code><code>:</code>

<code>number;</code>

<code>0</code><code>;</code>

<code>        </code><code>pmelist</code><code>=</code>

<code>[];</code>

<code>number !</code><code>=</code>

<code>1</code><code>:</code>

<code>            </code><code>p</code><code>=</code>

<code>number</code><code>/</code><code>primelist[i];</code>

<code>number</code><code>%</code><code>primelist[i];</code>

<code>r</code><code>=</code><code>=</code><code>0</code><code>:</code>

<code>                </code><code>pmelist.append(primelist[i]);</code>

<code>                </code><code>number</code><code>=</code>

<code>p;</code>

<code>p &lt; primelist[i]:</code>

<code>                    </code><code>pmelist.append(number);</code>

<code>pmelist;</code>

<code>                    </code><code>i</code><code>=</code>

<code>i</code><code>+</code> <code>1</code><code>;</code>

　　最后获得最大素因子

<code>def</code> <code>getthelargestprimefactorofnumber(</code><code>self</code><code>,number):</code>

<code>        </code><code>start</code><code>=</code>

<code>clock();</code>

<code>self</code><code>.getdecompositionfactors(number);</code>

<code>        </code><code>end</code><code>=</code>

<code>        </code><code>print</code>

<code>end</code><code>-</code><code>start;</code>

<code>pmelist[</code><code>len</code><code>(pmelist)</code><code>-</code><code>1</code><code>];</code>

　算法改进：