小练习：20171030 生成素数的整数

冬雪雪冬

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

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

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

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

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

这里已经有了500余题。

                               
登录/注册后可看大图

要求：

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

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

注重程序效率和创意。

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

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

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

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

                               
登录/注册后可看大图

357

考虑30的约数：1、2、3、5、6、10、15、30。
可以看出，对于30的每个约数d，d+30/d都是素数。

即：

1+30/1=31

2+30/2=17

3+30/3=13

5+30/5=11

6+30/6=11

10+30/10=13

15+30/15=17

30+30/30=31

都是素数。

存在不超过100 000 000的正整数n，使得对于n的每个约数d，d+n/d都是素数；求所有这样的数n的和。

jerryxjr1220

这题貌似很简单啊，我在手机上算的，也很快就算出来。由于1+n/1=1+n=质数，所以n必然是质数-1，只要计算1亿以下所有质数-1的数就可以了。
答案:1739023853137

1. def gen_primes(n):
   
2.   global primes
   
3.   primes=[1]*n
   
4.   primes[:2]=[0]*2
   
5.   for i in xrange(2,int(n**0.5+1)):
   
6.     if primes[i]:
   
7.       for j in xrange(i*i,n,i):
   
8.         primes[j]=0
   
9.   return [k-1 for k,v in enumerate(primes) if v]
   
10. lst = gen_primes(100000000)
    
11. def check(n):
    
12.   for i in xrange(2,int(n**0.5+1)):
    
13.     if n%i==0:
    
14.       if not primes[i+n//i]: return False
    
15.   return True
    
16. print sum(each for each in lst if check(each))

复制代码

口可口可

1. from numba import jit
   
2. 
   
3. @jit
   
4. def isPrime(num):
   
5.     if num <= 1:
   
6.         return False
   
7.     if num ==2:
   
8.         return True
   
9.     if num % 2 == 0:
   
10.         return False
    
11.     i = 3
    
12.     while i <= num**0.5:
    
13.         if (num % i == 0):
    
14.             return False
    
15.         i+=2
    
16.     return True
    
17. 
    
18. count=0
    
19. for n in range(1,100000000):
    
20.     for d in range(1,int(n**0.5+1)):
    
21.         if n%d == 0:
    
22.             if isPrime(d+n/d) == False:
    
23.                 break
    
24.     else:
    
25.         count+=n
    
26. 
    
27. print(count)

复制代码

结果是：1739023853137
但是运行时间很久...等看大神的高级算法

開汧吣伈

def isSushu(n):
    flag=True
    for i in range(2,n//2+1):
        if n%i==0:
            flag=False
            break
    return flag
'''
for i in range(2,20):
    if isSushu(i):
        print(i)
   
'''
for i in range(2,10000):
    flag1=True
    for j in range(1,i//2+1):
        if i%j==0:
            if   isSushu(int(j+i/j))==False:
                flag1=False
                break
    if flag1:
        print(i)


wo de xiao lv you man qing ci jiao  shu ru fa tu ran bu hao shi le       jian liang

gunjang

占楼。。。速度原来200s,改到40s左右
答案1739023853137

1. import time
   
2. import numpy as np
   
3. import itertools
   
4. 
   
5. st = time.time()
   
6. #n is square free,else if n=a*p^2 p+n/p=p+ap=p(1+a) is not prime
   
7. 
   
8. def solve(limit):
   
9.         primes = np.ones(limit, dtype=np.bool)
   
10.         for i in range(2, int(limit**0.5)+1):
    
11.                 if primes[i]: primes[i*i::i] = False
    
12.         primes[0], primes[1] = False, False
    
13.         plist = np.nonzero(primes)[0]
    
14.         #print(len(plist))
    
15.        
    
16.         def isSquareFree(n): #return True/False and prime factors
    
17.                 r = []
    
18.                 for p in plist:
    
19.                         if n%p == 0:
    
20.                                 n //= p
    
21.                                 if n%p == 0:
    
22.                                         return False, []
    
23.                                 r.append(p)
    
24.                                 if primes[n]:
    
25.                                         r.append(n)
    
26.                                         return True, r
    
27. 
    
28.         r = 3# 3.0 in 32bit
    
29.         for i in range(2, len(plist)): #5,7...
    
30.                 n = plist[i]-1
    
31.                 sf, pFactors = isSquareFree(n)
    
32.                 if sf:
    
33.                         for cnt in range(1, len(pFactors)//2 + 1):
    
34.                                 for cb in itertools.combinations(pFactors, cnt):
    
35.                                         pro = 1 #list mul
    
36.                                         for x in cb: pro *= x
    
37.                                         if not primes[pro + n//pro]:                                               
    
38.                                                 break
    
39.                                 else:
    
40.                                         continue
    
41.                                 break
    
42.                         else:
    
43.                                 r += n
    
44. 
    
45.         return r #overflow in 32bit
    
46. 
    
47. #print('%.20f'%solve(100000000)) # 1739023853137
    
48. print(solve(100000000))# 1739023853137
    
49. print('cost %fs'%(time.time()-st)) #100m cost 243s ==>77s => 41s

复制代码

wc365

1. #素数判断函数
   
2. def is_prime(n):
   
3.   if n < 2:
   
4.     return False
   
5.   for i in range(2, int(n**0.5+1)):
   
6.     if n%i == 0:
   
7.       return False
   
8.   return True
   
9. 
   
10. #判断正整数n是否符合要求
    
11. def fun(n):
    
12.     m = 1
    
13.     if n == 1:
    
14.       return True
    
15.     while m <= n:
    
16.         if n % m == 0 and n // m >= m: #m为n的约数
    
17.             if is_prime(m + n//m):
    
18.                 m += 1
    
19.                 continue
    
20.             else:
    
21.                 return False
    
22.         elif n % m != 0 and n // m >= m: # m不是n的约数
    
23.             m += 1
    
24.         else:
    
25.             return True
    
26. 
    
27. #（素数-1）生成器
    
28. def prime_generator(n):
    
29.   for x in range(n):
    
30.     if is_prime(x):
    
31.       yield x-1
    
32. 
    
33. # 计算和
    
34. def sumfun(n):
    
35.     total = 0
    
36.     for x in prime_generator(n):
    
37.         if fun(x):
    
38.             total += x
    
39.     return total

复制代码

结果：
>>> sumfun(100000000)
1739023853137

时间好久

nononoyes

#判断一个数是否是质数，如果是质数则返回true，否则返回false

def ifSimple(num):
#判断参数是否大于1

    if num > 1:
        # 查看因子
        for i in range(2,num):
            if(num%i==0):
                flag = False
                #print(flag,1)
                return flag
                break
        else:  
            flag = True
            #print(flag,2)
            return flag
   
    else:
        flag = False
        #print(flag,3)
        return flag


#求一个数的所有约数：
def getDivisor(x):
    divisor = []
    for i in range(1,x+1):
        if x%i==0:
            temple = [i]
            divisor.append(i)
    #print('divisor:',divisor)
    return divisor


#求符合要求的数：
def divisorIfSimple(num):
    result=0
    list = getDivisor(num)
    for d in list:
        if(ifSimple(int(d+num/d))==False):
            return result
            break
    else:
        result = num
        return result


求范围类符合要求的数字之和：
from builtins import range, int
from divisorIfSimple import *
from _ast import Num

def getSum(num):
    list = []
    for i in range(1,num+1):
        if(divisorIfSimple(i)!=0):
            list.append(i)
    return list   
        
        

if __name__ == "__main__":
     
     num = int(input("请输入一个正整数："))
     list = getSum(num)
     print("不大于%d的满足要求所有数的和为：%d"%(num,sum(list)))

Anner5

1. '''
   
2. 答案：111894087333395
   
3. 耗时：168.62847995758057
   
4. 
   
5. 思路：
   
6. 1、生成10**8的素数列表；
   
7. 2、筛选10**8的素数列表中为素数一次幂乘积的素数；
   
8. 3、对不符的*1x3x2+1类型素数求和；
   
9. 4、求和结果
   
10. 说明：2、3点为在100以内验证所得
    
11. 运行结果：
    
12. 110.41659569740295
    
13. 162.73110127449036
    
14. 111894087333335
    
15. 164.10227394104004
    
16. '''
    
17. import time
    
18. from itertools import *
    
19. startTime = time.time()
    
20. n=10**8
    
21. compositeNumberList = [None] * (n+1)
    
22. compositeNumberList[0] = True
    
23. primeNumber = []
    
24. k=2
    
25. while k <= n:
    
26.     if not compositeNumberList[k]:
    
27.         primeNumber.append(k)
    
28.         j = 2
    
29.         while k * j <= n:
    
30.             compositeNumberList[k * j] = True
    
31.             j +=1
    
32.         
    
33.     k +=1
    
34. a ={}
    
35. a = a.fromkeys(primeNumber,False)
    
36. b = []
    
37. i=0
    
38. while i < len(primeNumber):
    
39.     x = primeNumber[i]
    
40.     if not a[x]:
    
41.         b.append(x)
    
42.         j = 1
    
43.         while x ** 2 * j +1 <= primeNumber[-1]:
    
44.             a[x ** 2 * j +1] = True
    
45.             j +=1
    
46.         
    
47.     i +=1
    
48. y=0
    
49. for each in b:
    
50.     if int(str(each)[-1]) ==1 and y*6 < b[-1]:
    
51.         y +=each
    
52. print(sum(b)-len(b)-y*6)
    
53. print(time.time()-startTime)
    
54. 
    
55. 
    
56. 
    

复制代码

mrchenqi1981

'累死了我的CPU
import math

def isPrime(n):
    if n == 1:
        return False
   
    for i in range(2, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            return False

    return True

def check(num):
    for i in range(1, num + 1):
        if (num % i == 0):
            if (not isPrime(i + int(num / i))):
                return False

    return True

def sum(n):
    result = 0
    for i in range(n + 1):
        if (check(i)):
            result += i

    return result