【每天进步一点点】Python解题笔记（03篇）

jerryxjr1220

今天我们继续来看“欧拉计划”的第3题：求600851475143的最大因子。

解这题之前，我们先来看几种求质数的方法。为什么要知道求质数的方法呢？因为任何合数的因子都是由质数构成的，我们只有先求得最大质数，才能进行判定是否是这个合数的因子。

方法1：暴力穷举
比如要求n之内的所有质数，我们只需要从n-1开始，依次往下测试，如果i不能被任何>1且<=i-1的数整除的话，那么i就是质数。这个是最基本的方法，但是也是最慢的方法，尤其对于数量级比较大的数，几乎就算不出来了。

方法2：有条件穷举
虽然也是穷举，但是我们需要对测试的范围进行限定，比如我们可以直接从i**0.5开始往下测试，而不用从i-1开始，原因可以自己思考一下，很容易理解。其次，质数除2以外都是奇数，所以大于2的偶数都可以跳过不需要考虑了，这样又可以减少非常多的候选数了（其实3的倍数也可以筛选掉）。

1. def gen_primes(n):
   
2.         primes = [2,3,5]
   
3.         for i in range(7,n,2):
   
4.                 if i % 3 == 0: continue
   
5.                 flag = True
   
6.                 for j in range(5, int(i**0.5+1), 2):
   
7.                         if i % j == 0:
   
8.                                 flag = False
   
9.                                 break
   
10.                 if flag:
    
11.                         primes.append(i)
    
12.         return primes

复制代码

方法3：标记法
方法2的条件穷举速度上已经快了很多，但是还有更快的。标记法的逻辑是先建立全数列，然后按等差数列批量运算，例如先把除2以外的2的倍数的数列全部标记出来，再把除3以外的3的倍数全部标记出来，由于4（2的倍数）已经标记了，再把除5以外的5的倍数全部标记出来。。。依次类推，最后未被标记的数就是质数，原因也很容易理解吧。
由于，标记法是批量运算，所以速度比一个一个数字去判断又要快上许多。
结合numpy数组的话，速度可以再上一个台阶，求100万以内的质数列表，也只需1s以内。

1. import numpy as np
   
2. def gen_primes(n):
   
3.         primes = np.ones(n, dtype='int8')
   
4.         for i in range(2,int(n**0.5+1)):
   
5.                 if primes[i]:
   
6.                         primes[i*i::i] = 0
   
7.         return np.nonzero(primes)[0][2:]

复制代码

方法4：直接调用第三方库algorithms
algorithms库包含了非常多实用的数学工具，这部分以后会单独讲解。今天我们就先直接调用它，虽然速度不见得比我们用标记法算得快，但好处是你不需要自己去编写函数了，只要会调用就好。

1. from algorithms.math.sieve_atkin import atkin
   
2. print(atkin(1000000))

复制代码

有了那么多方法，再来计算这道题目就易如反掌了。
首先我们看一下，我们最大需要生成多大的质数列表，600851475143**0.5=775146... 我们只需取到775147即可。然后依次从质数列表中取质数（从大往小取）与600851475143取模，如果能整除，则这个数就是600851475143的最大因子。
一行代码输出：

1. from algorithms.math.sieve_atkin import atkin
   
2. print([prime for prime in atkin(775147)[::-1] if 600851475143 % prime == 0][0])

复制代码

如果我们要追求速度的话，1s以内就可以出答案了。

1. import numpy as np
   
2. def gen_primes(n):
   
3.         primes = np.ones(n, dtype='int8')
   
4.         for i in range(2,int(n**0.5+1)):
   
5.                 if primes[i]:
   
6.                         primes[i*i::i] = 0
   
7.         return np.nonzero(primes)[0][2:]
   
8. for prime in gen_primes(775147)[::-1]:
   
9.         if 600851475143 % prime == 0:
   
10.                 print(prime)
    
11.                 break

复制代码

你学会了吗？

～风介～

支持jerryxjr1220大佬！

jerryxjr1220

～风介～ 发表于 2017-8-21 11:32
支持jerryxjr1220大佬！

受宠若惊

还不知道我这半瓶子水还能晃荡多久

～风介～

jerryxjr1220 发表于 2017-8-21 11:36
受宠若惊

还不知道我这半瓶子水还能晃荡多久

说到水，俺现在已经变成万金油来着~

jerryxjr1220

～风介～ 发表于 2017-8-22 09:56
说到水，俺现在已经变成万金油来着~

这个系列是不是太简单了？好像没什么人有兴趣啊

不过我觉得我分享的这些解题方法都是我提炼过的，哪怕以后解很难的题，也是运用这些基础的方法。

好纠结啊！

～风介～

jerryxjr1220 发表于 2017-8-22 21:03
这个系列是不是太简单了？好像没什么人有兴趣啊

不过我觉得我分享的这些解题方法都是我提炼 ...

其实不是这个原因来着 —— 论坛的受众主要是初学者，大都对算法不是很感兴趣来着。

jerryxjr1220

～风介～ 发表于 2017-8-23 14:42
其实不是这个原因来着 —— 论坛的受众主要是初学者，大都对算法不是很感兴趣来着。

但是算法是基础啊，没有算法基础就算学会编程语言也写不出好的程序来。

你看我的其他几篇很火的帖子，什么画铅笔画啦，keras人工智能啦，都是靠算法在后面做基础的，不然单单告诉你一个模块也写不出东西来。

那你觉得这个系列还要写下去么？如果大家都不是很感兴趣的话。

～风介～

jerryxjr1220 发表于 2017-8-23 17:01
但是算法是基础啊，没有算法基础就算学会编程语言也写不出好的程序来。

你看我的其他几篇很火的帖子 ...

个人建议还是先把“鱼C论坛Python精英挑战赛”办好吧

jerryxjr1220

～风介～ 发表于 2017-8-23 17:47
个人建议还是先把“鱼C论坛Python精英挑战赛”办好吧

好吧，那就先告一段落了。

等以后看情况再说吧。

～风介～

jerryxjr1220 发表于 2017-8-23 19:23
好吧，那就先告一段落了。

等以后看情况再说吧。

做内容不是一蹴而就的事情，好好加油吧~

1173419450

个人觉得还不错呀。支持一波！！！