小练习 20170626 求有序根函数的第k个元素

冬雪雪冬 · 发表于 2017-6-26 09:28:53

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

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

x

本帖最后由冬雪雪冬于 2017-7-3 11:04 编辑

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

登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即7.3 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

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

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

题目：

n 的根函数，rad(n)，定义为其所有不同质因子之积。例如，504 = 2³ × 3² × 7，所以 rad(504) = 2 × 3 × 7 = 42。

如果我们对 1 ≤ n ≤ 10 计算 rad(n)，然后先根据 rad(n) 的值排序，如果 rad 值相同再根据 n 排序，我们得到：

登录/注册后可看大图

令 E(k) 为排序之后的第 k 个 n 值，例如， E(4) = 8， E(6) = 9。

如果将 1 ≤ n ≤ 100000 的 rad(n) 按照上述方法排序，求 E(10000)。

达锅 · 发表于 2017-6-26 12:19:57

本帖最后由达锅于 2017-7-1 22:59 编辑

'''
n 的根函数，rad(n)，定义为其所有不同质因子之积。例如，504 = 23 × 32 × 7，所以 rad(504) = 2 × 3 × 7 = 42。
如果我们对 1 ≤ n ≤ 10 计算 rad(n)，然后先根据 rad(n) 的值排序，如果 rad 值相同再根据 n 排序，我们得到：
令 E(k) 为排序之后的第 k 个 n 值，例如， E(4) = 8， E(6) = 9。
如果将 1 ≤ n ≤ 100000 的 rad(n) 按照上述方法排序，求 E(10000)。
'''
import time
t=time.time()
kk,nn=10000,100000
'''
zs=[0,0]+[1]*(nn-1)
for i,j in enumerate(zs):
if j==1:
for k in range(i,nn+1,i):
zs[k]*=i
zs[1]=1
print(sorted([(j,i) for i,j in enumerate(zs)])[kk][1])
'''
zs=[0,0]+[1]*(nn-1)
for i,j in enumerate(zs):
if j:
for k in range(i*i,nn+1,i):
zs[k]=0
zs=[i for i,j in enumerate(zs) if j]
xl=[i for i in range(nn+1)]
for i,j in enumerate(xl):
if j in zs:continue
p=1
ls=j//2
for k in zs:
if ls<k:break
p*=k if j%k==0 else 1
xl[i]=p
xl[0]=0
#for tt in range(kk):
print (sorted([(j,i) for i,j in enumerate(xl)])[kk][1])
print(time.time()-t)

复制代码

崩溃，正常方法运行了5分钟…………

21417
260.83691906929016

复制代码

jerryxjr1220 · 发表于 2017-6-26 22:42:39

本帖最后由 jerryxjr1220 于 2017-6-26 22:48 编辑

这题的解题思路，有正反2种解题方法。一般正向求解的话就是把每个数求rad（），然后比较大小排序。
我是反着考虑的，先把所有数的rad值设为1，然后从2开始每隔i乘以i，原理同标记法求质数一致。
这样就能非常快的得到一个rad的list，然后只需对这个list排序即可。
我用了numpy库，为了加快数组的运算速度。

import time, numpy
tst = time.time()
L = numpy.ones(100001, dtype=int)
for i in range(2,100001):
if L[i] == 1:
L[i::i] *= i
print(sorted([(L[x], x) for x in range(100001)], key=lambda pair: pair[0])[10000][1])
print(time.time()-tst)

复制代码

答案：
21417
0.1009361743927002

备注：因为我的list里面包含0，所以排序的时候要用10000，而不是9999。

小剑剑 · 发表于 2017-6-27 10:05:43

走光了斑竹

小剑剑 · 发表于 2017-6-27 10:05:46

走光了斑竹

WelanceLee · 发表于 2017-6-27 14:32:13

import math
import time
def f(n):
p = [2]
for i in range(3, n+1):
for each in p:
if i%each == 0:
break
if each > math.sqrt(i):
p.append(i)
break
return p
def h(a, p):
x = []
for each in p:
if a%each == 0:
a = a//each
x.append(each)
if each > a:
break
return x
def m(b):
s = 1
for each in b:
s *= each
return s
start = time.time()
n = 100000
p = f(n)
mid = time.time()
d = dict((i, m(h(i, p))) for i in range(1, n+1))
d = sorted(d.items(), key = lambda x: x[1])
print(d[9999][0])
end = time.time()
print('use time %.2f s: '%(end - start))

复制代码

我主要分四步，一是在范围内求质数表，二是求质因数列表，三是求积（根函数），最后在范围内排序。
答案是21417，时间运行有点长，9s左右~

飘飞的白杨 · 发表于 2017-6-27 14:56:06

筛法求素数，求出来的素数的倍数包含一个质因子为这个素数

k = 10000
N = 100000+1
l = []
for i in range(N):
l.append([1, i])
for i in range(2, N):
if l[i][0] == 1: # rad等于1，则是质数
l[i][0] = i
for j in range(2*i, N, i): # 求出包含质因数i的数
l[j][0] *= i
l.sort()
print(l[k])

复制代码

qq413317226 · 发表于 2017-6-27 18:07:34

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习 20170626 求有序根函数的第k个元素

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

评分

评分

点评

评分

评分