时间戳

首页 > 解决方案 > 关于内存使用和 for 循环的简单 Python 问题

python - 关于内存使用和 for 循环的简单 Python 问题

问题描述

我目前正在学习使用 python 作为课堂语言的密码学课程介绍。

我们遇到的问题非常简单，它要求我们做的就是找出传递给函数的某个整数 n 的最小素数除数，并将返回所述素数。

我们正在使用的 IDE 告诉我，由于内存不足，程序不断被中断。

下面是我的代码：

    def smallest_prime_divisor(n):
        if(n%2==0):
            return 2;
        for i in range(3, n):
            if(n%i==0):
                if(is_prime(i)):
                    return i;
    return n;

    for n in range(1,120):
        x=2^n;
        x+=1;
        smallest_prime_divisor(x)

我不认为问题出在 minimum_prime_divisor 函数上，而是在我的第二个 for 循环中的某个地方，因为我只使用了很多数字

    smallest_prime_divisor(x); #where x is equal to all integers 1-20

我知道这似乎是一个简单的问题，但它让我很生气，我似乎无法找到合适的词来搜索谷歌以获得正确的答案。

标签： pythoncryptography

解决方案

您的问题可能与您的is_prime()函数有关，如果我不得不猜测的话，它是递归调用自身。这是is_prime使用Wilsom 定理的一个实现，它将在不返回内存错误的情况下运行。

from math import factorial

def is_prime(n):
    return factorial(n - 1)  % n == n - 1

def smallest_prime_divisor(n):
    if(n%2==0):
        return 2
    for i in range(3, n):
        if(n%i==0):
            if(is_prime(i)):
                return i
    return n

for n in range(1,120):
    # Notice this line as well 'Paritosh Singh' mentioned in the comments why it is ** and not ^.
    x=2**n
    x+=1
    smallest_prime_divisor(x)

注意 和 之间的x=2^n变化x=2**n。

推荐阅读