`
rokuan
  • 浏览: 20412 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
社区版块
存档分类
最新评论

Project Euler每帖一题(005)

阅读更多
题目:
引用
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


这个题目解得很差,写了个函数,传入1到10,速度还行,传入1到20,竟然计算了XX秒...看来算法太烂了,自我笔试下@@@@

我的python代码:
def gcd(list):
    n = max(list)
    flag = True
    i = 1
    while True:
        for j in list:
            if (n * i) % j != 0:
                flag = False
                break
        if flag:
            return n * i
        else:
            flag = True
        i += 1
        
print gcd(range(1,21))


看了别人的解法,选了个比较大的基数,思路差不多:
i = 9699690 # Continuation.9699690=2*3*5*7*11*13*17*19
while 1:
	print "Testing: %s" % i
	for x in range(1, 21):
		print "%s:" % x,
		if i % x != 0:
			print "Fail"
			break
		else:
			print "Pass"
	else:
		print "Solution: %s" % i
		break
	i+=9699690


一种比较好的解决方案,核心思想是利用分解质因数来求解最大公倍数:
num = 20
'''
isSolved = False
i = 0
while not isSolved:
    for ii in range(2,num+1):
        if i % ii == 0 and i != 0:
            if ii == num: isSolved = True
        else:
            i = i + num
            break
print 'Lowest divisor: ', i
'''
 
def isPrime(a):
    prime=True
    for i in range(2,a):
        if (a % i == 0): prime=False
    if prime: return True
    else: return False
 
factorz = []
primeFactorz = []
def getPrimeFactors(a):
    gotFactor = False
    for ii in range(2,a+1):
        if a % ii == 0:
            gotFactor = True
            b = a/ii
            if isPrime(ii): factors.append(ii)
            else: getPrimeFactors(ii)
            if isPrime(b) and b != 1: factors.append(b)                
            else: getPrimeFactors(b)
        if gotFactor: break
 
for i in range(2,num+1):
    factors=[]
    getPrimeFactors(i)
    factorz.append(factors)
 
print 'Printing Factors of 2 through', num
for i in factorz:
    print i
 
new=[]
total=[]
def getHighestPow(a):
    counthigh = 0
    for i in factorz:
        count = 0
        for ii in i:
            if ii == a:
                count = count + 1
        if count > counthigh:
            counthigh = count
    if a not in new:
        new.append(a)
        total.append(a**counthigh)
 
for i in factorz:
    for ii in i:
        getHighestPow(ii)
 
sum=1
for i in total:
    sum = sum * i
 
print 'Lowest Common Multiple: ', sum
分享到:
评论

相关推荐

    Project Euler 第22题

    【标题】"Project Euler 第22题"是一个著名的编程挑战,源自Project Euler网站,这是一个鼓励人们通过编程解决数学和计算问题的在线平台。这道题目通常涉及到字符串处理、排序以及数学计算,旨在锻炼编程者的问题...

    下载Project Euler题目

    Project Euler是一个在线平台,提供了大量的数学和计算机科学问题,旨在提高编程技能和数学理解。这些问题通常需要高效的算法来解决。 描述中提到的“NULL”没有提供额外信息,但博文链接指向了一个ITEYE博客条目。...

    ProjectEuler 解题表格

    1. **问题编号**:每个Project Euler问题都有一个唯一的数字编号。 2. **问题描述**:简短概述问题的主题和目标。 3. **解决方案语言**:你使用的编程语言,如Python、Java、C++等。 4. **代码**:一段或几段实现...

    ProjectEuler1-16代码

    Project Euler是一个在线平台,它提供了一系列的数学和计算机科学问题,旨在通过解决这些问题来提升编程技能和数学理解。 首先,Project Euler的前16个问题涵盖了一系列基础和进阶的算法。这些问题可能涉及到: 1....

    project euler problem 5

    题目:Project Euler问题5——寻找最小公倍数 在Project Euler的问题集中,问题5要求我们找到能被1至20所有数字整除的最小正整数。这个问题实际上是在寻找这组数字的最小公倍数(LCM)。对于较小的参数值,如本例中...

    project euler5.rar_ACM_project

    这个压缩包包含了多个C++源代码文件,每个文件对应一个特定的Project Euler问题。 【描述】"project euler代码库第五部分(已测试通过)"表明这些代码是用于解决Project Euler系列问题中的第五部分题目,而且所有的...

    project euler欧拉工程1-50题代码golang版

    全部在linux下运行通过并得到结果,因为是个人所做,所以不保证是最优结果,仅供交流学习 因为是个人联系所做,所以代码中没有注释,不过我相信只要你真的有去思考题目也是能知道我为什么这样做 ...

    project euler1.rar_ACM_project_project euler

    【项目欧拉(Project Euler)】是一个非常受欢迎的在线数学和计算机编程挑战平台,它吸引着全球的程序员和数学爱好者参与。项目欧拉的问题通常涉及数学、算法和计算机科学,鼓励解决问题并学习新技能。本压缩包...

    Project-Euler:来自projecteuler.net的练习题

    Project-Euler 来自projecteuler.net的练习题 其他信息和链接:

    Project Euler_Eulerproject_fasmg_x86_windows_math_

    文件列表中包含了多个问题的源代码,如P011.asm至P021.asm,这些文件分别对应Project Euler的第11到21题。让我们逐一分析这些题目所涵盖的知识点: 1. P003.asm(最大质因数):此问题涉及到素数的检测和分解,需要...

    project euler2.rar_ACM_project

    "project euler2.rar_ACM_project" 是一个压缩包,包含了多个已经测试通过的C++源代码文件,用于解决Project Euler的第二部分问题。 文件名与对应的Project Euler问题关联,如152.cpp对应问题152,189.cpp对应问题...

    Euler project(1-5).zip

    这个"Euler project(1-5).zip"压缩包包含了前五个问题的MATLAB解决方案,每个问题都对应一个".mlx"文件。这些文件是MATLAB Live Scripts,是一种集代码、文本、图像和输出于一体的交互式文档格式,便于学习和理解...

    project euler3.rar_ACM_project

    Project Euler是一个著名的在线数学与计算机科学问题集,旨在挑战编程者的思维能力和算法技巧。在这个压缩包"project euler3.rar_ACM_project"中,包含了10个已经通过测试的C++源代码文件,分别是224.cpp、265.cpp、...

    projecteuler.net:我对 Project Euler 问题的一些解决方案

    这个压缩包可能包含了作者解决 Project Euler 题目的源代码,每个问题的解决方案可能作为一个单独的Java文件存在,文件名可能对应于问题的编号或题目描述的一部分。 对于使用Java来解决Project Euler的问题,我们...

    matlab用不同编程语言实现的各种Project Euler问题的解决方案.zip

    在压缩包内的“Project-Euler_main.zip”中,包含了具体的MATLAB源码文件,每个文件对应Project Euler的一个问题。通过阅读和理解这些源码,不仅可以学习到MATLAB的基本语法和高级特性,还可以了解到如何将数学思维...

    project-euler:多种语言的projecteuler.net问题解决方案

    在这个"project-euler-master"目录下,我们可以期待找到一系列按问题编号排列的Kotlin源代码文件,每个文件对应Project Euler中的一个问题。这些问题涵盖了基础数学、数论、几何、概率等多个领域,通过解决这些问题...

    ProjectEuler:projecteuler.net

    欧拉计划(Project Euler)是一个在线平台,旨在通过一系列具有挑战性的数学和计算机科学问题来提升编程技巧。这些问题设计巧妙,通常需要运用到数学、算法和编程知识来解决。参与欧拉计划,不仅可以锻炼编程能力,...

    ProjectEuler:Project Euler 问题的解决方案

    "Project Euler: Project Euler 问题的解决方案"是一个与编程挑战相关的项目,主要集中在使用JavaScript解决数学和计算问题。Project Euler是一个著名的在线平台,它提供了一系列的数学和计算机科学问题,旨在提升...

    Project-Euler:projecteuler.net 上问题的解决方案

    在这个名为 "Project-Euler-master" 的文件夹中,很可能包含了多个子文件或子文件夹,每个都对应着 Project Euler 的一个问题。这些问题可能包括但不限于数字理论、组合数学、几何、计算几何、概率、动态规划等众多...

    project-euler-solutions:我在 Project Euler 中所有问题的答案

    项目欧拉解决方案该存储库包含我对 Project Euler (projecteuler.net) 上发现的编程问题的所有答案。 每个解决方案都是用 Java 编写的,旨在从命令行运行。 解决方案文件中将提供指向相关欧拉问题的链接。 某些解决...

Global site tag (gtag.js) - Google Analytics