Codility每周一课：L10 Prime and compo

0.png

P10.2 MinPerimeterRectangle

Find the minimal perimeter of any rectangle whose area equals N.

• P10.2 最小周长
  计算面积为N的矩形的最小周长

整数N，表示某个矩形的面积。边长为A和B的矩形的面积为AB，周长2（A+B）。找到面积等于N的任何矩形的最小周长。该矩形的边均为正整数。

例如，给定整数N=30，面积为30的矩形有：

• （1，30）：周长62；
• （2，15）：周长34；
• （3，10）：周长26；
• （5，6）：周长22；

编写函数：

def solution(N)

给定整数N，则返回面积恰好等于N的所有矩形中的最小周长。

例如，给定一个n=30的整数，函数应该返回22，如上所述。

假定：

1. N是区间[1，100000000]内的整数；

• 解题思路

从不大于N的平方根的数开始遍历，只要找到N的因子，就返回。因为越往后所得的周长越大。边长接近平方根的矩形的周长是最小的。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 10：Prime and composite numbers
# P 10.2 MinPerimeterRectangle


def solution(N):
    """
    返回面积为N的所有矩形的最小周长,时间复杂度O(sqrt(N))
    :param N: 正整数N
    :return: 返回矩形的最小周长
    """
    for i in range(int(N ** 0.5), 0, -1):
        if N % i == 0:
            return 2 * (i + int(N / i))

• 结果
  image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image