质数查找器 - 优化 [英] Prime number finder - optimization

问题描述

我正在尝试构建一个尽可能快的素数查找器.这是程序中包含的 def 函数.我在一个细节方面遇到了问题，我已将其放在下面的 {brackets} 中.主要参数我也解释了.

I'm trying to build a prime number finder that would work as fast as possible. This is the def function that is included in the program. I'm having problems with just one detail, which I have put in {brackets} below. I have also explained the main parameters.

import math
def is_prime(x):
    c=0      #a simple counter
    a=7      #a (+ k*6)a group of all possible deviders of the number(if 2,3 and 5 are taken away)
    b=11      #the other group
    {r=x**(1/2)}      #root of the number
    {f=math.floor(r)}       #floor of the root
    if x%2!=0 and x%3!=0 and x%5!=0:      #eliminate all multiples of 2,3 and 5
        while (c==0 and {a<f}):         #while loop
                if x%a==0 or x%b==0:
                        c+=1          #if true -> will break
                a+=6        #adding 6 to a and b (numbers that have a potential to devide
                b+=6
        if c==0:       #if a number not divisable by anything, return number
            return x

此功能无法正常工作.如果不是我的数字的平方根，我只是用 x/3 替换它，它会工作得很好.但问题是我不想检查 x**(1/2) 和 x/3 之间的所有可能的分隔符，因为它只会减慢功能，没有别的.所以这是有效的代码:

This function doesn't work properly. If instead of floored squared root of my number I just replace it with x/3 it will work just fine. But the problem is that I don't want to check all the possible dividers in between x**(1/2) and x/3, because it will only slow the function, nothing else. So here is the code that works:

import math
def is_prime(x):
c=0
a=7
b=11
if x%2!=0 and x%3!=0 and x%5!=0:
        while (c==0 and a<x/3):
                if x%a==0 or x%b==0:
                        c+=1
                a+=6
                b+=6
        if c==0:
            return x

如果有人看到这个问题，请帮忙:D

If anyone sees the problem, help please :D

推荐答案

正如上面评论中指出的，python2 执行整数除法所以 1/2 == 0

As pointed out in the comment above, python2 performs integer division so 1/2 == 0

• 你可以把你的根写成:

• You can write your root as:

x**0.5

或使用 math.sqrt:

or using math.sqrt:

math.sqrt(x)

朴素素性测试可以这样实现:

The naive primality test can be implemented like this:

def is_prime(n):
    if n<=1: return False
    if n<=3: return True
    if not n%2 or not n%3: return False
    i=5
    while i*i<=n:
        if n%i==0: return False
        i+=2
        if n%i==0: return False
        i+=4
    return True

这篇关于质数查找器 - 优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！