小练习 20170717 连续正除数

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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 < 10⁷ 中，满足上述条件的 n 的个数。

达锅

抢沙发，暴力破解

1. 
   
2. import time as t#直接就想到了求质素的筛法,但是速度太慢,至少1分钟
   
3. tt=t.time()
   
4. n=1+10**6
   
5. 
   
6. li=[0 for i in range(n)]
   
7. li[1]=-1
   
8. for i in range(2,n):#n的倍数往后加1
   
9.     for j in range(i,n-1,i):
   
10.         li[j]+=1
    
11. 
    
12. print(sum(1 for i in range(2,n-1) if li[i]==li[i-1]))
    
13. print(t.time()-tt)

复制代码

换数组

1. 
   
2. import time as t#直接就想到了求质素的筛法~
   
3. import numpy as np
   
4. 
   
5. tt=t.time()
   
6. n=1+10**7
   
7. ar=(np.ones(n))
   
8. ar[1]=0
   
9. 
   
10. for i in np.arange(2,n//2+1):
    
11.     ar[i:n:i]+=1
    
12. 
    
13. #b=ar[1:]
    
14. #c=ar[:-1]
    
15. #d=np.where((b+c)/2-b==0)
    
16. #print(len(d[0]))
    
17. print(len(np.where((ar[1:]+ar[:-1])/2-ar[1:]==0)[0]))
    
18. print(t.time()-tt)
    

复制代码

那也要20秒……

1. 986262
   
2. 19.424811840057373

复制代码

jerryxjr1220

这题计算的逻辑应该是很简单的，唯一需要注意的就是运行效率，我用了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

機動翻車魚

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

复制代码

suloman

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)

RogerSun

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)