使用循环查找蛮力素数 [英] Using Loop to find Brute Force Prime Numbers

问题描述

我正在尝试编写一个使用循环的程序，在该程序中使用Mersenne查找Brute Force Prime Nu，床.方向如下.

I'm trying to write this program that uses looping where it finds Brute Force Prime Nu,beds using Mersenne. The direction is as follows.

素数是不能被其他任何数均分的数字(除琐碎的1外).确定数字是否为质数的所有已知方法都依赖于蛮力，即对可能性进行详尽的测试.编写例程以检查数字是否为质数.检查它是否是偶数，如果不是，请检查所有奇数，直到数字的平方根为止(您知道为什么平方根足够了吗?).如果数字不是素数，请告诉用户一个因素.

A prime number is a number that is not evenly divisible by any other number (except, trivially, 1). All known methods of determining whether a number is a prime number rely on brute force, that is, exhaustive testing of the possibilities. Write a routine that checks whether a number is prime. Check if it’s even, and if not, check all the odd numbers up to the square root of the number (do you see why the square root is enough?). If the number is not prime, tell the user one factor.

对于您的演示，您将使用Mersenne 67，它是2到67的幂减1(请参阅问题1-4-A):147573952589676412927 [147,573,952,589,676,412,927].1644年，马林·梅森(Marin Mersenne)认为这个数字是素数.直到1903年F.N.科尔解决了这个猜想，为此，他在美国数学学会的一次会议上获得了热烈的鼓掌.分辨率是多少?(即Mersenne 67是质数吗?)使用您的程序来回答此问题；您的程序可能会运行约2½分钟，比解决问题最初花费的2½个世纪大了很多.

For you demo, you’ll use Mersenne 67, which is 2 to the 67th power minus 1 (see problem 1-4-A): 147573952589676412927 [147,573,952,589,676,412,927]. In 1644, Marin Mersenne conjectured this number was prime. It was not until 1903 that F.N. Cole resolved this conjecture, for which he received a standing ovation at a meeting of the American Mathematical Society. What was the resolution? (i.e., is Mersenne 67 prime?) Use your program to answer this question; your program will probably run for about 2½ minutes, quite an advance over the 2½ centuries it originally took to resolve the issue.

这是我到目前为止所拥有的，但是似乎无法在我可以验证我的答案的地方进行.任何输入将不胜感激.预先谢谢你.

This what what I have so far, but it doesn't seem to run where I can verify my answer. Any inputs would greatly appreciated. Thank you in advance.

def me():
    N = int(input("What is the Value of N?="))
    Mersenne=(2**N)-1
    print(format(Mersenne,',d'))

me()

我该如何在上面包含Merseene代码?

How do I include the Merseene code above to this?

'''
This function takes a single argument n and returns either
1) a factor of n     if n is not prime
2) False             if n is prime
'''
def is_prime(n):
# "Check if it's even..."
if is_even(n):
    # (do something)
else:
    # "... and if not, check all the odd numbers up to the square root of the number"
    for f in <something that generates odd numbers>:
        if is_factor(f,n):
            # (do something)

# Default case:
#    n is odd, and 
#    none of the odd numbers up to sqrt(n) are factors of n
# (do something)


def get_n():
n = raw_input("What is the value of n? ")
return ((2 ** 67)-1) if n == 'm' else int(n)


n = get_n()  
p = is_prime(n)

if p:
  print("%d is not prime (e.g. factor=%d)" % (n, p))
else:
  print("%d is prime")

推荐答案

以下某些伪代码可能有帮助或无济于事

Here's some pseudocode that may or may not help

'''
This function takes a single argument n and returns either
    1) a factor of n     if n is not prime
    2) False             if n is prime
'''
def is_prime(n):
    # "Check if it's even..."
    if is_even(n):
        # (do something)
    else:
        # "... and if not, check all the odd numbers up to the square root of the number"
        for f in <something that generates odd numbers>:
            if is_factor(f,n):
                # (do something)

    # Default case:
    #    n is odd, and 
    #    none of the odd numbers up to sqrt(n) are factors of n
    # (do something)


def get_n():
    n = raw_input("What is the value of n? ")
    return ((2 ** 67)-1) if n == 'm' else int(n)


n = get_n()
p = is_prime(n)

if p:
    print("%d is not prime (e.g. factor=%d)" % (n, p))
else:
    print("%d is prime")

请注意， is_even 和 is_factor 不是真正的函数，您必须自己实现它们或将其更改为等效操作.同样，<生成奇数的东西> 也不是真实的，

Note that is_even and is_factor are not real functions, you'd have to either implement them yourself or change them to equivalent operations. Also, <something that generates odd numbers> isn't real either, same thing.

此外， get_n()是一个小功能，提示用户输入整数并返回它.如果用户输入 m (单个小写字符)，则返回Mersenne 67(=(2 ^ 67)-1)

Also, get_n() is a little function that prompts a user for an integer and returns it. If the user enters m (the single, lower case character), then it returns Mersenne 67 (= (2^67) - 1)

这篇关于使用循环查找蛮力素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！