小练习：20171106 （素数-k）阶乘

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。

什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives

这里已经有了500余题。

                               
登录/注册后可看大图

要求：

以python语言完成，如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成，即11.13 10：00之前，其后将公开大家的答案，并评比成绩。

另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

-- 回帖需写明解题思路，鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难，为此略过一部分偏难的题目 --

                               
登录/注册后可看大图

381

取素数p，令S(p) = (∑(p-k)!) mod(p)，其中1 ≤ k ≤ 5。

例如，如果p=7，
(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872。
由于872 mod(7) = 4，所以S(7) = 4。

可以验证，对于5 ≤ p < 100，∑S(p) = 480。

对于5 ≤ p < 10⁸，求∑S(p)。

jerryxjr1220

1. #(p-1)!+(p-2)!+(p-3)!+(p-4)!+(p-5)!
   
2. #= (p-5)! * ((p-1)(p-2)(p-3)(p-4) + (p-2)(p-3)(p-4) + (p-3)(p-4) + (p-4) + 1)
   
3. #= (p-5)! * ((-1)(-2)(-3)(-4) + (-2)(-3)(-4) + (-3)(-4) + (-4) +1)
   
4. #= (p-5)! * (24 - 24 + 12 - 4 + 1)
   
5. #= (p-1)! / ((p-1)(p-2)(p-3)(p-4)) * 9
   
6. #= (p-1)! / (-1)(-2)(-3)(-4) * 9
   
7. #= (-1) * 3 / 8
   
8. #= (p-3) / 8 mod p
   
9. #利用费马小定理 a = b / 8 (mod p) => 8*a = b (mod p) => 8*8**(p-2)*a = 8**(p-2)*b (mod p) => 8**(p-1)*a = 8**(p-2)*b (mod p) => a = 8**(p-2)*b (mod p)= pow(8, p-2, p) * b

复制代码

1. import numpy as np
   
2. def s(p):
   
3.         return (p - 3) * pow(8, p-2, p) % p
   
4. primes = np.ones(10**8, dtype='int8')
   
5. for i in range(2, 10**4):
   
6.         if primes[i]:
   
7.                 primes[i*i::i] = 0
   
8. plist = np.nonzero(primes)[0][4:].tolist()
   
9. print(sum(s(p) for p in plist))

复制代码

139602943319822

qwc3000

"""
质数类
输出一个0--n范围的质数
"""
import math
class zhishu(object):
    def __init__(self, num):
        self.num=num

    # 判断是否是质数
    def isprime(self, i):
        # 如果为2或者3时 为质数
        if i == 2 or i == 3:
            return True
        # 不在6的倍数两侧的一定不是质数
        if i % 6 != 1 and i % 6 != 5:
            return False
        # 取num的平方根
        tmp = int(math.sqrt(i)) + 1
        # 在6的倍数的两侧的也可能不是质数
        for j in range(5, tmp, 6):
            if i % j == 0 or i % (j + 2) == 0:
                return False
        # 是质数
        return True
    # 是质数添加到质数列表
    def primelist(self):
        self.PrimeList=[]
        for i in range(1,self.num):
            # print(i)
            if self.isprime(i):
                self.PrimeList.append(i)
"""
阶乘 取余数
"""
class zhishu_jiecheng_quyu(object):
    def __init__(self,num):
        self.num=num
        self.tmp5=1
        self.tmp4=1
    # 计算n-5的阶乘
    # 可以由n-5的阶乘的余数再计算n-4的余数
    def n5_jiecheng_quyu(self):
        if self.num > 5:
           # 使用乘同余法 计算大数阶乘取余
           # 即：每次乘法的时候都取一次余数
           self.tmp5 = (self.num - 5) * (self.num - 6) % self.num
           for i in range(self.num-7, 0, -1):
               self.tmp5 = self.tmp5 * i % self.num
        else:
            self.tmp5=1
    # 计算n-4的阶乘
    def n4_jiecheng_quyu(self):
        self.tmp4 = self.tmp5 * (self.num - 4) % self.num
    # 计算 n-4 n-5 n-3的阶乘取余的和
    # n-3的阶乘对n取余的结果为：（n-1)/2
    # n-2的阶乘对n取余的结果为：1
    # n-1的阶乘对n取余的结果为：n-1
    # 所以n-1和n-2的余数和为n，对题干要求求和再取余，这两项可以直接舍去
    # 因此对于题目要求，可以只计算后三项的和再取余
    def quyu_qiuhe(self):
        self.he=(self.tmp4+self.tmp5+(self.num-1)/2)%self.num


ZS=zhishu(100000)
ZS.primelist()
P_List=ZS.PrimeList

tmp0=0
# 对质数列表进行取余求和 再取余 计算
for i in range(4,len(P_List)+1):
    tmp = P_List.pop()
    ZSQY=zhishu_jiecheng_quyu(tmp)
    ZSQY.n5_jiecheng_quyu()
    ZSQY.n4_jiecheng_quyu()
    ZSQY.quyu_qiuhe()
    tmp0=tmp0+ZSQY.he

print(tmp0)

阿Rui

学习学习
’

lomiss

虽然知道题中要求讲究创意与效率，但是无奈新手能力有限，只能这样了。
效率的话当大于10**4，就要跑112秒，所以10**8恐怕就不是一时半会了。
于是发出来想看看大神们如何实现高效率吧。

import time
import math
Present = time.time()
temp1 = []
Allsum = 0
Allsum1 = 0
term = 1
num1 = int(math.pow(10, 8))
for num in range(5, num1):
    temp = []
    while num != 1:
        for i in range(2, num + 1):
            if num % i == 0:
                temp.append(i)
                num //= i        # 依次找出能够整除的数，该数就是质因数
                break
    # for each in temp:
        # if each not in temp1:
            # temp1.append(each)
    # print(temp)  罗列出每个数的质因数
    if len(temp) == 1:
        temp1 += temp
# print(temp1)      罗列出5~100中所有的质数

'''def factorial(m):
    if m == 0: return 1
    if m == 1: return 1
    if m >= 2: return m * factorial(m - 1)'''  # 定义累乘函数

for each in temp1:
    for n in range(1, 6):
        m = each - n
        if m == 1:
            term = 1
        if m == 0:
            term = 1
        # term = factorial(m)   效率更低，用常规方法
        while m > 1:
            s = m * (m - 1)
            m -= 2
            term *= s
        Allsum += term
        term = 1
    remainder = Allsum % each     # 求余
    Allsum1 += remainder
    Allsum = 0
Now = time.time()
gap = Now - Present
print(Allsum1)
print("一共用时%.2f" % gap)