|
发表于 2017-10-23 09:50:50
|
显示全部楼层
本帖最后由 jerryxjr1220 于 2017-10-23 15:01 编辑
一开始写的程序,就是完全按照题目逻辑来,暴力解法,1000万的话,差不多15秒出结果。
- import math
- def gen_primes(limit):
- primes = [1]*limit
- for i in xrange(2,int(limit**0.5+1)):
- if primes[i]:
- for j in xrange(i*i,limit,i):
- primes[j]=0
- return [k for k,v in enumerate(primes) if v][2:]
- def get_max(p,q,n):
- mp = int(math.log(n,p)+1)
- mq = int(math.log(n,q)+1)
- maxi = 0
- for i in range(1,mp):
- for j in range(1,mq):
- if p**i*q**j>n: break
- maxi = max(maxi, p**i*q**j)
- return maxi
- def solve(N):
- result = 0
- plist=gen_primes(N//2)
- for i in xrange(len(plist)-1):
- for j in xrange(i+1,len(plist)):
- gm = get_max(plist[i],plist[j],N)
- if gm==0: break
- result += gm
- return result
- print solve(10000000)
复制代码
11109800204052
[Finished in 15.5s]
程序很容易写,逻辑清晰。
对这个程序做一下优化,get_max()函数分情况讨论,不用穷举所有组合,可以进一步缩短运算时间。
- import math
- def gen_primes(limit):
- primes = [1]*limit
- for i in xrange(2,int(limit**0.5+1)):
- if primes[i]:
- for j in xrange(i*i,limit,i):
- primes[j]=0
- return [k for k,v in enumerate(primes) if v][2:]
- def get_max(p,q,n):
- mp = int(math.log(n,p))
- mq = int(math.log(n,q))
- if p*q>n:
- maxi = 0
- elif q*q>n:
- maxi = p**mp*q
- while maxi>n:
- maxi//=p
- elif n**(1/3)<q<n**0.5 and (n/q)**0.5<p<q:
- maxi = p*q
- else:
- maxi = 0
- for i in range(1,mp+1):
- for j in range(1,mq+1):
- if p**i*q**j>n: break
- maxi = max(maxi, p**i*q**j)
- return maxi
- def solve(N):
- result = 0
- plist=gen_primes(N//2)
- for i in xrange(len(plist)-1):
- for j in xrange(i+1,len(plist)):
- gm = get_max(plist[i],plist[j],N)
- if gm==0: break
- result += gm
- return result
- print solve(10000000)
复制代码
11109800204052
[Finished in 7.6s]
用arrdio改写,并做个界面:
- import win.ui;
- import time;
- /*DSG{{*/
- var winform = win.form(text="Project Euler Calculation";right=460;bottom=278;border="thin";max=false)
- winform.add(
- button={cls="button";text="Calculate";left=120;top=182;right=334;bottom=233;font=LOGFONT(h=-27;weight=700);z=3};
- edit={cls="edit";left=135;top=117;right=423;bottom=158;edge=1;font=LOGFONT(h=-23;weight=700);multiline=1;z=2};
- limit={cls="edit";left=136;top=69;right=423;bottom=110;edge=1;font=LOGFONT(h=-23;weight=700);multiline=1;z=7};
- static={cls="static";text="Result";left=7;top=117;right=133;bottom=153;align="center";font=LOGFONT(h=-23;weight=700);transparent=1;z=1};
- static2={cls="static";text="Euler 347";left=21;top=21;right=216;bottom=58;font=LOGFONT(h=-27;weight=700;italic=255);transparent=1;z=4};
- static3={cls="static";text="Limit";left=7;top=72;right=133;bottom=108;align="center";font=LOGFONT(h=-23;weight=700);transparent=1;z=6};
- time_calc={cls="static";left=10;top=249;right=438;bottom=276;font=LOGFONT(h=-17);transparent=1;z=5}
- )
- /*}}*/
- var calc = function (limit) {
- var gen_primes = function (n) {
- var primes = {};
- for i=1;n table.push(primes,1);
- for i=2;n**0.5 {
- if primes[i] {
- for j=i*i;n;i primes[j]=0;
- }
- }
- var plist = {};
- for k,v in primes if v table.push(plist,k);
- table.remove(plist,1);
- return plist;
- }
- var get_max = function (p,q,n) {
- var mp=math.floor(math.log10(n)/math.log10(p));
- var mq=math.floor(math.log10(n)/math.log10(q));
- if p*q>n return 0;
- elseif q*q>n {
- max = p**mp*q;
- while max>n max/=p;
- return max;
- }
- elseif n**(1/3)<q and q<n**0.5 and (n/q)**0.5<p and p<q return p*q;
- else {
- max = 0;
- for i=1;mp {
- for j=1;mq {
- if p**i*q**j>n break;
- max = math.max(max,p**i*q**j);
- }
- }
- return max;
- }
- }
- var result = 0;
- var plst = gen_primes(limit/2);
- for x=1;#plst-1 {
- for y=x+1;#plst {
- var tmp = get_max(plst[x],plst[y],limit);
- if not tmp break;
- result += tmp;
- }
- }
- return result;
- }
- winform.button.oncommand = function(id,event){
- //winform.msgbox( winform.button.text );
- var st = time.tick();
-
- winform.edit.text = calc ( eval(winform.limit.text) );
- winform.time_calc.text = string.format('Total time used: %d ms',time.tick()-st);
- }
- winform.show()
- win.loopMessage();
复制代码
3.5秒出结果,同样的逻辑,果然还是python的运算效率拼不过啊。
换一种逻辑,不是依次测试每个质数对,而是改用标记法,把每个质数的倍数都标记出来。
- N=10**7
- def gen_primes(limit):
- primes = [1]*limit
- for i in xrange(2,int(limit**0.5+1)):
- if primes[i]:
- for j in xrange(i*i,limit,i):
- primes[j]=0
- return [k for k,v in enumerate(primes) if v][2:]
- plist=gen_primes(N)
- multiprime=[[i] for i in xrange(N+1)]
- for p in plist:
- for q in xrange(p,N+1,p):
- if not multiprime[q]: continue
- if len(multiprime[q]) >= 3:
- multiprime[q] = False
- else: multiprime[q].append(p)
- used = set()
- result = 0
- for i in xrange(N,-1,-1):
- if not multiprime[i]: continue
- if len(multiprime[i]) == 3:
- mark = (multiprime[i][1], multiprime[i][2])
- if mark not in used:
- used.add(mark)
- result += i
- print result
复制代码
差不多20多秒出结果。 |
评分
-
查看全部评分
|