小练习结果揭晓 squarefree的二项式系数

冬雪雪冬

原帖子：http://bbs.fishc.com/thread-93854-1-1.html
题目：

二项式系数 nCk 可以排成帕斯卡三角的形式，如下图：

                               
登录/注册后可看大图

可知，前 8 行中，总共有 12 个不同的数字 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 和 35。对于正整数 n，如果没有任何一个质数的平方可以整除 n，则 n 被叫做 squarefree 。
那么。帕斯卡三角的前 8 行得到的那 12 个不同的数字中，除了 4 和 20，其余都是 squarefree 的。所有 squarefree 数之和是 105。

请给出帕斯卡三角前 51 行中不同的 squarefree 数之和。

题目很简单，就是两个要点，组合和质数，计算组合可以用阶乘的公式也可以用加法一行行的算，加法会更快些。
本题的正确答案是：34029210557338
回答正确的鱼油是：
jerryxjr1220  0.404s
小Q学Python  0.5202s
plus              0.118s
小剑剑            0.218s
hhhhhq         12.458s
达锅               0.076s

用时最短的是：
达锅   

夏天和大熊

失之毫厘差之千里喽，把判断不满足条件的数直接从列表remove。结果结果差了好多！！代码也写了不够简练，重新改了一遍。参考的小Q的算法。在求杨辉三角中的数时利用对称性以列为单位，只求了一半。

1. # 给出卡帕斯三角中前n行中所有不同的数
   
2. def crt_list(n = 3):
   
3.     list_nums = [[1 for i in range(n)]]
   
4.     list_kap = [1]
   
5.     if n%2 :
   
6.         temp = n//2
   
7.     else:
   
8.         temp = n//2 - 1
   
9.     for i in range(temp):
   
10.         list_deff = list_nums[i]
    
11.         list_column = [1]
    
12.         for j in range(1, n-i-1):
    
13.             num = list_column[-1] + list_deff[j]
    
14.             list_column.append(num)
    
15.             if num not in list_kap:
    
16.                 list_kap.append(num)
    
17.         list_nums.append(list_column)
    
18.     return list_kap
    
19. 
    
20. # 给出i_end以内的素数表            
    
21. def crt_pri(i_end):
    
22.     mark_pri = [True for i in range(i_end + 1)]
    
23.     mark_pri[0], mark_pri[1] = False, False
    
24.     for i in range(2, i_end + 1):
    
25.         if mark_pri[i] == True:
    
26.             for j in range(i + i, i_end + 1, i):
    
27.                 mark_pri[j] = False
    
28.     nums_pri = [i for i,j in enumerate(mark_pri) if j == True]
    
29.     return nums_pri
    
30. 
    
31. 
    
32. 
    
33. # 将所给列表中满足squarefree条件的数加起来
    
34. def sum_sqarefree(n = 51):
    
35.     list_og = crt_list(n)
    
36.     t_start = t.time()
    
37.     list_re = []
    
38.     list_pri = [i*i for i in crt_pri(int(max(list_og)**0.25) + 1)]
    
39.     for each in list_og:
    
40.         for i in list_pri:
    
41.             if each < i:
    
42.                 break
    
43.             if each%i == 0:
    
44.                 list_re.append(each)
    
45.                 break
    
46.     t_end = t.time()
    
47.     print(t_end - t_start)
    
48.     return sum(set(list_og) - set(list_re))

复制代码