Project Euler Problem 276, 268, 347

〇〇

〇〇 发表于 2012-2-9 12:18
如果q为质数，那么范围内的所有p都是可以的，也可以不计算
SQL> exec q3702(1000)
4:6:9

但是质数之占1/ln(n),影响有限

tree_new_bee

〇〇 发表于 2012-2-9 12:51
但是质数之占1/ln(n),影响有限

是的。
按互质的一些规律去排除一些数很容易， 比如：
*质数与任何数互质
*相邻数互质
*相邻的奇数互质。。。

但都减少不了多少工作量。 因为这些数即使调用gcd函数，也是很快能循环结束的。

tree_new_bee

用Q73的筛法( http://www.itpub.net/forum.php?m ... 69&pid=17121256 )来做， 因为避免了gcd和mod操作，能稍快些。

1. create or replace procedure q370c(arg number default 1e6) is
   
2. 
   
3.   q integer;
   
4.   p integer;
   
5.   sm integer:=0;
   
6.   type typen1 is table of boolean index by pls_integer;
   
7.   type typen2 is table of typen1 index by pls_integer;
   
8.   frac typen2;
   
9. begin
   
10.   
    
11.   for q in 3 .. sqrt(arg/2) loop
    
12.     for p in ceil((sqrt(5)-1)/2*q) .. q-1 loop
    
13.         frac(q)(p) := true;
    
14.     end loop;
    
15.   end loop;
    
16.   q:=frac.first;
    
17.   while q<=sqrt(arg/2)/2 and q is not null loop
    
18.     p:=frac(q).first;
    
19.     while p is not null loop
    
20.       for k in 2..sqrt(arg/2)/q loop
    
21.         if frac.exists(q*k) then frac(q*k).delete(p*k); end if;
    
22.       end loop;
    
23.       p:=frac(q).next(p);
    
24.     end loop;
    
25.     q:=frac.next(q);
    
26.   end loop;
    
27.   sm:=0;
    
28.   q:=frac.first;
    
29.   while q is not null loop
    
30.     p:=frac(q).first;
    
31.     while p is not null loop
    
32.       --if p+q > q*q/p then
    
33.       sm:=sm+floor(arg/(p*p + p*q + q*q));
    
34.       --end if;
    
35.       p:=frac(q).next(p);
    
36.     end loop;
    
37. 
    
38.     q:=frac.next(q);
    
39.   end loop;
    
40.   sm:=sm+ floor(arg/3);
    
41.   dbms_output.put_line('total: '||sm);
    
42.   end q370c;

复制代码

SQL> exec q370c(1e6)

total: 861805

PL/SQL procedure successfully completed

Executed in 0.297 seconds

SQL> exec q370c(1e7)

total: 9712598

PL/SQL procedure successfully completed

Executed in 4.446 seconds


OO上面那个p/q>(sqrt(5)-1)/2=0.618，很强，有了这个， 试验了下不加a+b>c的条件，也能得到正确结果，但不知这样可靠不可靠。

〇〇

tree_new_bee 发表于 2012-2-9 15:41
用Q73的筛法( http://www.itpub.net/forum.php?mod=redirect&goto=findpost&ptid=1383369&pid=17121256 )来 ...

只要gcd法1/4的时间，半个数量级

lastwinner

tree_new_bee 发表于 2012-2-9 13:09
是的。
按互质的一些规律去排除一些数很容易， 比如：
*质数与任何数互质

质数与任何数互质
————————————这个说法不对哦

tree_new_bee

集合的next()和exists()开销都比较高，
所以前面的delete操作改成修改状态。
这样改动又能提高了半个数量级的性能。

1. create or replace procedure q370d(arg integer default 1e6) is
   
2.   q integer;
   
3.   p integer;
   
4.   sm integer:=0;
   
5.   type typen1 is table of boolean index by pls_integer;
   
6.   type typen2 is table of typen1 index by pls_integer;
   
7.   frac typen2;
   
8. begin
   
9.   for q in 3 .. sqrt(arg/2) loop
   
10.     for p in ceil((sqrt(5)-1)/2*q) .. q-1 loop
    
11.         frac(q)(p) := true;
    
12.     end loop;
    
13.   end loop;
    
14.   for q in 3..sqrt(arg/2)/2 loop
    
15.     for p in ceil((sqrt(5)-1)/2*q) .. q-1 loop
    
16.       for k in 2..sqrt(arg/2)/q loop
    
17.           frac(q*k)(p*k):=false;
    
18.       end loop;
    
19.     end loop;
    
20.   end loop;
    
21.   sm:=0;
    
22.   for q in 3 .. sqrt(arg/2) loop
    
23.     for p in ceil((sqrt(5)-1)/2*q) .. q-1 loop
    
24.      if frac(q)(p) then
    
25.       sm:=sm+floor(arg/(p*(p+q)+q*q));
    
26.      end if;
    
27.    end loop;      
    
28.   end loop;
    
29.   sm:=sm+ floor(arg/3);
    
30.   dbms_output.put_line('total: '||sm);
    
31.   end q370d;

复制代码

这次甚至可以尝试1e8了：

SQL> exec q370d(1e6)

total: 861805

PL/SQL procedure successfully completed

Executed in 0.094 seconds

SQL> exec q370d(1e7)

total: 9712598

PL/SQL procedure successfully completed

Executed in 0.796 seconds

SQL> exec q370d(1e8)

total: 108073540

PL/SQL procedure successfully completed

Executed in 8.127 seconds

SQL>

tree_new_bee

lastwinner 发表于 2012-2-9 20:16
质数与任何数互质
————————————这个说法不对哦

呵呵，有误。 其实我想说的是质数与任何比它小的数互质。