鱼C论坛

 找回密码
 立即注册
查看: 2148|回复: 5

[技术交流] 小练习 20170717 连续正除数

[复制链接]
发表于 2017-7-16 18:55:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-7-24 11:35 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives
这里已经有了500余题。


                               
登录/注册后可看大图


题目要求:
以python语言完成,如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成,即7.24 10:00之前,其后将公开大家的答案,并评比成绩。

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

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


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





题目:

对于某些整数 n,n 和 n+1 有着相同个数的正除数(因子),比如 14 的因子有 1,2,7,14, 而 15 的有 1,3,5,15。

请找出 1 < n < 107 中,满足上述条件的 n 的个数。










想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-16 21:45:26 | 显示全部楼层
本帖最后由 达锅 于 2017-7-22 22:43 编辑

抢沙发,暴力破解

  1. import time as t#直接就想到了求质素的筛法,但是速度太慢,至少1分钟
  2. tt=t.time()
  3. n=1+10**6

  4. li=[0 for i in range(n)]
  5. li[1]=-1
  6. for i in range(2,n):#n的倍数往后加1
  7.     for j in range(i,n-1,i):
  8.         li[j]+=1

  9. print(sum(1 for i in range(2,n-1) if li[i]==li[i-1]))
  10. print(t.time()-tt)
复制代码


换数组

  1. import time as t#直接就想到了求质素的筛法~
  2. import numpy as np

  3. tt=t.time()
  4. n=1+10**7
  5. ar=(np.ones(n))
  6. ar[1]=0

  7. for i in np.arange(2,n//2+1):
  8.     ar[i:n:i]+=1

  9. #b=ar[1:]
  10. #c=ar[:-1]
  11. #d=np.where((b+c)/2-b==0)
  12. #print(len(d[0]))
  13. print(len(np.where((ar[1:]+ar[:-1])/2-ar[1:]==0)[0]))
  14. print(t.time()-tt)
复制代码


那也要20秒……

  1. 986262
  2. 19.424811840057373
复制代码


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-7-16 22:48:35 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-7-20 17:45 编辑

这题计算的逻辑应该是很简单的,唯一需要注意的就是运行效率,我用了numba.jit神器和numpy来加速,6秒左右可以出答案。不用神器的话,用时要翻4倍,20多秒出答案。
  1. import time, numba, numpy
  2. @numba.jit('int32(int32)')
  3. def solve(limit):
  4.         master = numpy.ones(limit, dtype='int16')
  5.         for i in range(2, limit):
  6.                 master[i::i] += 1
  7.         c = 0
  8.         for n in range(1, limit-1):
  9.                 if master[n] == master[n+1]:
  10.                         c += 1
  11.         return c
  12. print(solve(10**7))
  13. print('Time used: %.3f sec' % (time.process_time()))
复制代码

986262
Time used: 6.516 sec
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-7-17 15:50:53 | 显示全部楼层

  1. l = [ ]
  2. k = [ ]
  3. m = n + 1
  4. for n in range (1, 10000000):
  5.     for a in range(1, n+1):
  6.         if n%a == 0:
  7.             l.append(a)
  8. for m in range(1, 10000000):
  9.     for b in range (1, m+1):
  10.         if m%b == 0:
  11.             k.append(b)
  12. if len(l) == len(k):
  13. print(n)
  14. print(m)

复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-7-17 22:53:09 From FishC Mobile | 显示全部楼层
count=0
count2=0
for i in range(3,100):
    temp=i
    count1=count
    count=0
   
    for j in range(2,int(i/2)+1):
        
        if temp%j==0:
            count+=1
    if count==count1:
        count2+=1
        print(i,"    ",i-1)
print (count2)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-7-20 21:02:02 | 显示全部楼层
import math
for n in range(2,10**7-1):  # 设置n的取值范围
    cnta = 0
    cntb = 0
    for i in range(2,int(math.sqrt(n))+1):   # 取到平方根整除即可,从2开始就可以了,1每个数都可以整除
        if n%i == 0:
            cnta += 1
    if (int(math.sqrt(n)))**2 == n:
        cnta = cnta * 2 -1
    else:
        cnta = cnta * 2

    for i in range(2,int(math.sqrt(n+1))+1):   # 取到平方根整除即可,从2开始就可以了,1每个数都可以整除
        if (n+1)%i == 0:
            cntb += 1
    if (math.sqrt(n+1))**2 == n+1:
        cntb = cntb * 2 -1
    else:
        cntb = cntb * 2
    if cnta == cntb:
        print(n)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 06:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表